8299308548

7 Relacje automatyczne

Zdefiniujmy funkcję l: {0,1}* —> N jako: l(e) = 0, l(0w) = 2l(w), l(lw) = 2l(w) + 1.

Dla liczby naturalnej k zdefiniujmy £*, = {0, l}^fc.

Dla liczb naturalnych j < k zdefiniujmy funkcję IT[. : ££ —* {0,1}* jako: II{.(c) = e, IIfc((oi,a2,...aj,...afc)iw) = ajll£(u;), gdzie (ai, a₂, ...aj,... a^) € £&.

Relację R C N^fc nazwiemy na tej liście zadań automatyczną, jeśli język Lr złożony z tych słów w € ££, dla których zachodzi f?(/(Il{.(«;)), l(U.^(w)),... Z(n£(iu))), jest regularny.

Zadanie 43. Czy relacja dodawania jest automatyczna? Przez relację dodawania rozumiemy tu {(a, b, c) G N³ : a + b = c}.

Zadanie 44. Czy relacja mnożenia jest automatyczna? Przez relację mnożenia rozumiemy tu {(a,b,c) G N³ : ab = c}.

Zadanie 45. Udowodnij, że rzut relacji automatycznej jest relacją automatyczną. Innymi słowy, jeśli R C N^fc jest relacją automatyczną, to również relacja R' = {r G N^fe_1 : 3m G N (r, m) G R} jest relacją automatyczną (dla uproszczenia możesz przyjąć, że k — 2).

8 Gramatyki bezkontekstowe i automaty ze stosem

Zadanie 46. Zbuduj automat ze stosem rozpoznający język dobrze rozstawionych nawiasów dwóch rodzajów generowany przez gramatykę:

S^SS|(S)|[S]|_E

która ma jeden symbol nieterminalny S i cztery symbole terminalne (,),[,].

Zadanie 47. Zbuduj gramatykę bezkontekstową generującą język:

L — {w G {0,1}* : |to|o = 2|w|i A |ui|i jest liczbą parzystą}.

Zadanie 48. Czy język L = {w G (0,1}* : |to|o ^ |w|i < 2|w|o} jest bezkontekstowy?

Zadanie 49. Czy język L — {w G {0,1}* : 3n € N 2n|w|o < |u>|i < (2n + l)|w|o} jest bezkontekstowy?

Zadanie 50. Podaj algorytm rozstrzygający dla danej gramatyki bezkontekstowej G, czy L{G) jest niepusty.

Zadanie 51. Pokaż, że L C {0}* jest bezkontekstowy wtedy i tylko wtedy gdy jest regularny.

Zadanie 52. Niech G będzie gramatyką generująca poprawnie zbudowane formuły rachunku zdań ze zmiennymi zdaniowymi p i q. Symbolami terminalnymi w G są p, q, (,),    =>, zaś

produkcjami S —> ~'iSj(S^l =*> 5)|p|ę

Znajdź gramatykę w postaci normalnej Chomsky’ego generującą ten sam język.

Zadanie 53. Czy język L3 = {w G {0,1,2}* : ->3x G {0,1,2}* w = xx} jest bezkontekstowy?

Zadanie 54. Czy dopełnienie języka L3 z poprzedniego zadania, język Lą = {w € {0,1,2}* : 3x G {0,1,2}* w = xx} jest bezkontekstowy?

Wskazówka: (1) rozważ język LąC\ L gdzie L = Lo* 10* 10* 10* 1 •

(2) Skorzystaj z lematu o pompowaniu, pamiętaj że podział w = sztyx, którego istnienie postuluje lemat jest taki, że \zty\ < c, gdzie c jest stałą z lematu.

7