Photo 0007

Automaty i Gramatyki Zestaw III-B

Kolokwium, 7 grudzień 2007

Zadanie 1. Podaj wyrażenie regularne odpowiadające językowi złożonemu ze słów naci alfabetem {0,1} które zawierają podsłowo 0010 lub które składają się tylko / jednego rodzaju symboli (same literki 0 lub same 1).

Zadanie 2. Podaj deterministyczny automat skończony odpowiadający jęz> ko w i złożonemu ze słów nad alfabetem {0, 1} które nie zawierają podslowa 110.

Zadanie 3. Wyeliminuj r-przejściu a następnie zdetei minizuj następujący lutom u

	a b (
-» F 1	2 2
2	3 3
3	4
4	1

Zadanie 4. Zadanie 5. Zadanie G.

Podaj automat skończony opisany wyrażeniem regularnym (10r|;01)\ Podaj gramatykę bezkontekstową generującą język {a^J"6"‘a*ⁿ|U < n.m Podaj automat stosowy akceptujący język {a^r,t-’^,‘o"‘| 1 < n,m}.