- Definiti o gramatica Chomsky, explicand semnificatia fiecareia dintre componentele sale.
- Definiti relatia de derivare generala din cadrul unei gramatici.
- Definiti formele propozitionale din cadrul unei gramatici.
- Definiti limbajul generat de o gramatica (se vor explica toate elementele care apar in definitie).
- Fie gramatica G1 = ( {S,A,B},{a,b}, P,S), avand regulile de productie P definite prin:
S → aB|bA
A → a|aS|bAA
B → b|bS|aBB
si fie dat cuvantul σ = aaabbabbba.- Sa se determine tipul gramaticii. Argumentati.
- Sa se gaseasca o derivare la stanga si una la dreapta pentru σ.
- Sa se verifice daca gramatica este ambigua (se va defini ce este o gramatica ambigua).
- Fie gramatica G2=({S1},{c,d}, P={S1→S1cS1c|d},S1). Sa se construiasca gramatica ce genereaza reuniunea limbajelor generate de gramaticile G1 si G2.
- Care este forma normala Chomsky pentru productiile unei gramatici de tip 2?
- Modelul matematic al automatului finit (elemente, configuratie, miscare, functie de tranzitie, AF determinist si nedeterminist, limbaj acceptat).
- Fie gramatica G=({S,A,B}, {a,b}, P,S) cu P={S→aA|aB, A→aA|b,B→bA}
Sa se construiasca automatul finit care accepta limbajul generat de G si sa se reprezinte matricea de tranzitii si diagrama de tranzitii a automatului construit. Automatul nu trebuie sa fie determinist. Se va prezenta si principiul de constructie in general. - Automatul Push-Down (model fizic, model matematic, APD determinist si nedeterminist, configuratie, miscare, criterii de acceptare a sirurilor, limbaj recunoscut de un automat Push-Down).
- sa se construiasca un APD echivalent cu GIC avand productiile {S→0AB|B1A, A→BB|0, B→AA|1} de mai jos si sa se indice miscarile efectuate asupra sirului 10001.
- Sa se gaseasca gramatica care genereaza limbajul peste alfabetul {b,c}, format din multimea tuturor cuvintelor avand 3 simboluri de "c" consecutive, oriunde in secventa.
Puteti lasa si voi variantele voastre la aceasta materie, in comentariile acestei pagini.