Zdjecia 0054

CfytyH.

Automaty i Gramatyki

Egzamin

2007/2008

>

ie przez podano wzorce od kszego (w sensie zawierania

E~J

-h ) -h

)

r/

*a*

⁾L^J ⁵)

4.

wyrażeń regular-z nie języki.

u

Czy następująca gramatyka jest jednoznaczna? S —* aSb | bSci | bb

Czy    w    następującej    gramatyce

można    wyprowadzić    puste    słowo?

•S —* XXX, X —► ab\ ba \ e

•    • •

Czy    w    następującej    gramatyce

można    wyprowadzić    słowo    a bab?

S —> aSa | bSb | ab

Czy    język    generowany    przez następującą    gramatykę jest skończony?

. S -» 55 | bSb | ab

Czy następująca gramatyka generuje pusty język? S —> SS | SbS \ aSb

• • •

•    * • *

Eliminacja £-przejść w automacie skończonym może spowodować kwadratowy wzrost liczby krawędzi.

W gramatykach 1 >ezkontekstowych, w prawych stronach produkcji może być co najwyżej po jednym nieterminalu.

Zęby gramatyka bezkontekstowa była jednoznaczna, to każde słowo musi mieć w niej co najwyżej jedno drzewo wyprowadzenia.

W automatach stosowych inoEćyj wać ^-przejścia.    ^jgj|§H|