Testeaza-ti cunostintele la limbaje formale


  1. Definiti o gramatica Chomsky, explicand semnificatia fiecareia dintre componentele sale.
  2. Definiti relatia de derivare generala din cadrul unei gramatici.
  3. Definiti formele propozitionale din cadrul unei gramatici.
  4. Definiti limbajul generat de o gramatica (se vor explica toate elementele care apar in definitie).
  5. 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.
    1. Sa se determine tipul gramaticii. Argumentati.
    2. Sa se gaseasca o derivare la stanga si una la dreapta pentru σ.
    3. Sa se verifice daca gramatica este ambigua (se va defini ce este o gramatica ambigua).
    4. 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.
  6. Care este forma normala Chomsky pentru productiile unei gramatici de tip 2?
    1. Modelul matematic al automatului finit (elemente, configuratie, miscare, functie de tranzitie, AF determinist si nedeterminist, limbaj acceptat).
    2. 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.
    1. 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).
    2. 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.
  7. 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.
COMENTARII

optional (nu va fi afisat pe website)
max: 255 caractere


Acest site utilizeaza cookie-uri. Navigand in continuare va exprimati acordul asupra folosirii cookie-urilor.