Limbaje Formale si Automate · 2016 · Sesiune
- Profesor
- Lorina Negreanu
- Anul examenului
- 2016
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- TOATE
- Adăugat
- 2 februarie 2017 de anonim
1. Fie L1,L2 limbaje. Notam L=L1L2={w|exista x în L2 a.i. wx este în L1}. Dem ca dacă L1 e LR, atunci L e LR. (Aici greșeala era ca au uitat sa menționeze ca și L2 e LR.)
2. Scrie o expresie regulata pentru limbajul L((aub)a*) interested L(baa*). Justificare.
3. Fie doua GIC.G1 și G2, care generează L1 și L2. Demonstrează ca L={s1s2..snt1t2...tn /cu si din. L1 SI ti din L2} este LIC.
4. Cum este L={a^nb^mc^k/k=|m-n|}?
5. Fie L un limbaj format doar din stringul s.
s=1 dacă extratereștri exista
s=0 altfel.
Este L Turing Decidabil? Justificați.
6. Scrie lema de pompare pentru LIC.
2. Scrie o expresie regulata pentru limbajul L((aub)a*) interested L(baa*). Justificare.
3. Fie doua GIC.G1 și G2, care generează L1 și L2. Demonstrează ca L={s1s2..snt1t2...tn /cu si din. L1 SI ti din L2} este LIC.
4. Cum este L={a^nb^mc^k/k=|m-n|}?
5. Fie L un limbaj format doar din stringul s.
s=1 dacă extratereștri exista
s=0 altfel.
Este L Turing Decidabil? Justificați.
6. Scrie lema de pompare pentru LIC.