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