EGZAMIN zerowy – Języki automaty i obliczenia.  

Zadania. 

Zad 1. Przekształcid podaną gramatykę (reguły produkcji), aby była monotoniczna i posiadała 
najmniejszą liczbę reguł. 

S → AD | SA | DC | lambda 
A → CA | 0 
B → B1 | BB 
C → CD | BA 
D → 

Zad 2. Język L generowany jest za pomocą gramatyki G = < {S, A, B, 0, 1}, {0, 1}, P, S > o następujących 
regułach produkcji: 

S → 0A | 1B 
A → 0B | 1A | 0 
B → 0S | 11 | 1 

Czy podany język jest (odpowiedzi uzasadnid): 

a.)  Regularny. 
b.)  Bezkontekstowy. 
c.)  Kontekstowy. 
d.)  Rekurencyjnie przeliczalny. 

Zad 3. Wyznaczyd gramatykę regularną opisującą język (wykres gramatyki, zbiór reguł produkcji). 

L = | a* (b + bb)(ab)* | 

Zad 4. Dana jest gramatyka G = < {A, B, a, b}, {a, b}, P, A > o następującym zbiorze reguł produkcji: A: 
A → AB | Aa | a;  B: bA | BB | Ba | b. Przekształcid podaną gramatykę G do postaci normalnej 
Greibach. 

Zad5. Automat Moore`a podany jest w tabeli: 

Stan 

a 

b 

c 

WY 

1 

2 

1 

2 

X 

2 

2 

1 

3 

Y 

3 

2 

3 

3 

Z 

 

a.)  Napisz układ równao, z którego można wyznaczyd R

21

 

b.)  Wyznacz R

21