1. feladat
a.) Készítsen a reguláris kifejezéssel adott nyelvet elfogadó NFA-t!
b.) Szerkesszen ezzel az NFA-val ekvivalens DFA-t!
c.) Minimalizálja a kapott DFA-t!
d.) Adjon meg egy olyan, legalább 6 betűből álló szót, amelyet elfogadnak ezek az automaták! Igazolja tranzíciós fával, hogy az a.) részben kapott NFA elfogadja ezt a szót!
2. feladat
Legyen adott a G = (V, T, P, S) környezetfüggetlen nyelvtan, ahol V = {A, B, C, D, S}, T = {a, b} és a produkciós szabályok a következők:
a.) Küszöbölje ki a nyelvtanból a felesleges szimbólumokat! (Indokolja a lépéseket!)
b.) Írja fel az a.) résznél kapott nyelvtant Chomsky-féle normálalakban!
c.) Írja fel az a.) résznél kapott nyelvtant Greibach-féle normálalakban! A c.) rész nem kötelező az aláírásért. Viszgán plusz egy jegyet ér, ha jól megcsinálja valaki legalább 2-es érdemjegy esetén.
d.) Adjon meg 3 olyan szót, ami előállítható ezekkel a nyelvtanokkal!