LFA (si pentru IFR) - Curs din saptamana a 7-a [pg 37]

Buna ziua si bine ati venit


Va rog sa aveti iarasi manualul de Limbaje formale si teoria automatelor la indemana, deschis la pagina  37. (nr paginii tiparite).


Faptul ca exista o ierarhie a gramaticilor, ierarhia lui Chomsky, induce o ierarhie a limbajelor. De ce, manualul nu spune, dar fiecare limbaj are o gramatica cu numar maxim. Fireste, toate limbajele decidabile ar putea avea, fiecare, o gramatica generala de tip 0. Dar daca un limbaj are o gramatica de tip 3 il vom pune la categoria limbaje de tip 3.


Cititi definitia 1.12 pg 37

In unele manuale clasele limbajelor

- dependente de context

- independente de context

- regulare

se noteaza cu L indice 1, L indice 2, L indice 3, indici inferiori, iar L-ul este un L rond, rotunjit, ca R de la numere reale.


Cititi exemple si observatii pg 37 (pg 39 in pdf).

1) La o gramatica este dificil sa faci analiza ssintactica sau un parser pentru a gasi simbolul epsilon, adica sirul vid "". Cum il recunoastem in sirul de intrare ?

Ei bine, daca totusi limbajul contine si sirul vid (si sunt limbaje dde programare chiar la care puteti compila fisierul cu text vid si obtineti codul NOP;RETURN) ,

atunci vom inventa o regula ca el sa se obtina direct din simbolul de start,

S -> ε

si vom curata celelalte reguli de prezenta lui. Metoda e in paragraful 5.3 , sustine autorul cartii.

2)Se constata imediat ca limbajele regulare sunt si independente de context, vezi forma regulilor din gramatica, eda face ca regulile de la tipul 3 sa fie si reguli de la tipul 2 de gramatici. Deci L indice 3 inclus in L indice 2. Iar Limbajele monotone sunt limbaje generale deci L indice 1 inclus in L indice 0.

Dati pagina la pagina 38. (40 in pdf).
3) de ce genereaza gramaticacu regula S -> aS limbajul vid ? Fiindca singura sa regula nu poate sa scape de neterminalul S din sirul formt de oricate ori ai aplica-o, derivand:
S => aS => aaS => aaaS samd
din pacate textul final va fi format numai din terminali.

4) Gramatica de la acest puncyt genereaza limbajul cu un singur cuvant vid, fie ca il notam cu epsilon sau cu "".
Cum: Aplic regula S->"" si obtin L={ "" } , limbajul cu un singur cuvant, si acela vid.

5) Un limbaj finit are de asemenea o gramatica evidenta de tipul al treilea. E suficient sa scriu reguli rand pe rand care produc acele texte:

L = {x,y,z,t}

S-> x
S-> y
S-> z
S -> t

unde x y z t pot fi patru texte oarecare in caest exemplu.
6) Limbajul format cu toate cuvintele cu toate literele peste algfabetul sigma, notat cu sigma si *, este un limbj chiar de tip 3.

Este suficient sa luam toate literele acelui alfabet sigma, am sale notez a,b,c,d - e mai simplu - ca la alfabetul nostru si punem regulile:
S-> aS
S->bS
S->cS
...
S->zS
apoi un S-> "" (sau il notati cu epsilon pe "").

Exercitiu: Cu aceasta gramatica generati cuvantul "hello" !
S=> hS => heS => helS => hellS => helloS => hello
Ce regula am aplicat la fiecare pas ?

Aplicatie: (pg 38 carte, pg 40 pdf) Gramatica Identificatorilor.
Scrieti ogramatica ce genereaza identificatorii formati dintr-o litera si litere sau cifre in continuare.

I -> L
I -> C
I -> IC
I -> IL

Ce inseamna aceste reguli ?

C -> 0 | ... | 9
L -> A | ... | Z | a | ... | z.

Aplicati regulile pentru a obtine identificatorul r2d2.
I => IC => ILC => ICLC => LCLC => rCLC =>r2LC =>r2dC =>r2d2
Ce reguli am aplicat :
3,4,3,1, 6,5,6,5. Verificati. 

Cititi va rog dumneavoastra 1.5 pg 39.
Inafara de reprezentarile propuse, pe care va rog sa le studiati, ce reprezentare am folosit pentru a reprezenta gramatica limbajului Simple pe intelesul bison-ului ?

Pauza s-a terminat, va rog sa trecem la alt capitol:

AUTOMATE FINITE
Voi incepe o postare noua pe blog. Manualul deschis la pg 47 (pg49 pe pdf).