1. gyakorlat

1. feladat Mit jelent az alábbi két kifejezés? (a+b)*(aa+bb)(a+b)* (ab)+ 2. feladat Készíts nyelvtant az alább definiált nyelvekre! Azon mondatok összessége, melyek tartalmazzák a baba részszót. (Szigma={a,b}) Szigma={a,b} A mondatok páros hosszúságúak. A helyes zárójelezések nyelve: a nyelv mondatai csak nyitó és csukó zárójeleket tartalmaznak, és megfelelõ számban és sorrendben állnak. 3. feladat Milyen nyelvet generál az alábbi nyelvtan? S -> aA | bB | b A -> aS | bC B -> aC | bS C -> aB | bA | a 4. feladat Igaz-e, hogy minden véges nyelv reguláris? A véges nyelv attól véges, hogy csak véges sok mondata van. 5. feladat Milyen nyelvet generál az alábbi nyelvtan és melyik nyelvosztályba tartozik? (Indoklást is kérek.) S -> aB | bA A -> bAA | aS | a B -> aBB | bS | b 6. feladat Adott az alábbi nyelvtan (Szigma={0,1}): S -> 00A | BA | 00D | 11D A -> BS | CE | CS B -> 11 C -> 0D0 D -> epszilon Milyen nyelvet generál? Lehet-e 3-as típusú nyelvtannal generálni? 7. feladat Adjunk CF nyelvtant az alábbi nyelvekhez! {aibi | i <= j <= 3i } {aibjck | i, j, k >= 1 and (i=j or j=k or i=k)} 8. feladat Mit generál az alábbi nyelvtan? S -> S1S2 | epszilon S1 -> aS1b | epszilon S2 -> bS2c | epszilon 9. feladat Mit generál az alábbi nyelvtan? S -> aSBC | abC CB -> BC bB -> bb bC -> bc cC -> cc 10. feladat Hány generatív nyelvtan van? Hány generatív nyelv van? Hány reguláris nyelv van?

Varró Gergely gervarro@cs.bme.hu

Utolsó módosítás dátuma: 2004. február 10.