1109144855

5 Gramatyki bezkontekstowe i automaty ze stosem

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

S —* SS|(S)|[$]|e

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

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

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

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

Zadanie 43. Czy język L = {w 6 {0,1}* : 3n € N 2n|tu|o < |w|i < (2n + l)|iw|o} jest bezkontekstowy?

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

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

Zadanie 46. 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 —► -iS|(S => 5)|p|<?

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

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

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

Wskazówka: (1) rozważ język LąC\ L gdzie L = Lq- 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.

Zadanie 49. Zbuduj NDPDA i gramatykę bezkontekstową G dla języka {0,1}* — {www :

e {0.1}*}.

Zadanie 50. (Za 3 punkty, bardzo trudne) Czy istnieje gramatyka bezkontekstową generująca zbiór tych słów nad alfabetem {0,1}, które nie są postaci vww dla żadnych słów w, v, takich że |i>| = |w|

Zadanie 51. Czy język L złożony z tych wszystkich słów nad alfabetem {0,1}, które są postaci wvw, dla pewnych słów w,v, takich że |«;| = |u| jest bezkontekstowy?

Zadanie 52. Czy język L będący dopełnieniem języka L z poprzedniego zadania do {0,1}* jest bezkontekstowy?

Zadanie 53. Czy język L = {vww : v,w € {a,b,c}*,w e} jest bezkontekstowy?

Zadanie 54. Niech L₌ będzie językiem tych słów nad alfabetem {0,1}, które mają tyle samo zer co jedynek, a Lr niech będzie językiem wszystkich palindromów. Czy przekrój L- z dopełnieniem Lr jest językiem bezkontekstowym? (mamy tu na myśli dopełnienie do {0,1}*)

Zadanie 55. Niech L₌ będzie językiem tych słów nad alfabetem {0,1}, które mają tyle samo zer co jedynek, a Lr niech będzie językiem wszystkich palindromów. Czy przekrój L= z Lr jest językiem bezkontekstowym?