IMGG61

Automaty i Gramatyki Zestaw III-A

Kolokwium, 7 grudzień 2007

Zadanie 1. Podaj wyrażenie regularne odpowiadające językowi złożonemu ze słów nad alfabetem {a, b) w których pierwszy i ostatni znak są różne lub które składają się tylko z literek b.

Zadanie 2. Podaj deterministyczny automat skończony odpowiadający językowi złożonemu ze słów nad alfabetem {o, b} które nie zawierają podsłowa aba.

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

Zadanie 3. Wyeliminuj e-przejścia a następnie zdeterminizuj następujący automat

Zadanie 4. Podaj automat skończony opisany wyrażeniem regularnym a'b’{ad)^m. Zadanie 5. Podaj gramatykę bezkontekstową generującą język jo^fcl^2fc0²ⁿ|0 < A:,nj. Zadanie 6. Podaj automat stosowy akceptujący język |o^fclⁿ0²ⁿ|l < fc.nj.