Photo 0010

Automaty i Gramatyki Zestaw III-A

Kolokwium, 7 grudzień 2007

Zadanie 1. Podaj wyrażenie regularne odpowiadające je/ykowi złożommu • słów mui alfabetom {u,6} w których pierwszy i ostatni znak stf lóżnr In!) któu kłid.ij^ >\*_: tylko z literek b,

Zadanie 2. 1 *odaj drtriministyczny aut,ornat skończony odpowiadają y jy/.\ k • i - lo/..rp n u ze słów nad alfabetom {a, 6} które nie zawierają podslowa obo.

Zadanie 3. Wyeliminuj c przejścia a następnie zdetonninizig uastrpuja<\ automat

	a b c
— 1	2
F 2	3 3
3	4 4
4	1

Zadanie 4. Podaj automat skończony opisany wyrażeniem regularnym a'b'(aa \ Zadanie 5. Podaj gramatykę bezkontekstową generującą język {o* 1^'U^2,,|0 < k. n}

Zadanie 6. Podaj automat stosowy akceptujący język jo*r0²ⁿ|l < k. ej.