Model Examen LFA

—– partial I ——– 22.11.2011
Definiti automatul determinist, limbajul acceptat de un automat determinist, automat pushdown si forma redusa a gramaticilor dependente de context.     3p.
Cum se aplica regulile de stergere? 2p
Relizti un automat care sa genereze limbajul de mai jos si justificati succinct raspunsul. 2p
L={ua(la puterea n)b(la puterea k)c(la puterean), u = {a,b}*,n,k>0}
Descrieti o gramatica care sa genereze limbajul de mai jos si justificati succinct raspunsul. 2p
L={a(la puterea 2i)b(la puterea n)c(la puterea k)d(la puterea n), i>=0, n,k>1}

——

1. Scrieti def gramaticii, limbajului acceptat, simbol inutil si gramatici de tip1

2. scrieti cum de transforma un automat de pushdown det intr-o gramatica

3. Scrieti un automat pt expresia (a|b)*| (a ori b) si explicati succint cum ati ajuns la solitie

4. Scrieti o gramatica pentru limbajul a^n * b^k * c^2n * d^l , n>=1, k,l>=0 si explicat cum ati gandit solutia.

Multumim, Șoșu Liviu si Simona Serseniuc!