EGZAMIN zerowy by Pepsi v0 11

background image

EGZAMIN zerowy – Języki automaty i obliczenia.

ODPOWIEDZI PODLEGAJĄ DYSKUSJI !!

//Pepsi®

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

Tutaj chyba czego

ś brakuje (?)


Wyszukiwarka

Podobne podstrony:
Egzamin 2k08 by Pepsi v1
Egzamin 2k08 by Pepsi v1
Egzamin 2k09 odp by Pepsi v2
egzamin psi by?epfrez
Historia Polski XX wieku Materiały do egzaminu historia polski XXw wykład! 11 12
Egzamin chemia nieorganiczna pytania czerwiec 11
Egzamin zerowy (1)
egzamin dr Radomski, POSTĘPOWANIE ADMINISTRACYJNE(11)
Lista lektur na egzamin zerowy
Egzamin zerowy BIOLOGIA 2009
egzamin zerowy 2011a
Pytania na PKM Egzamin zerowy, SiMR, PKM, Egzamin, PKM egzamin
egzamin fiz by qra
materiały na egzamin, egzamin, opr by offca, METODY PRACY HODOWLANEJ - Pytania na egzamin:
Egzamin gleby?ited by 3
egzamin zerowy zarz strategiczne !, Zarządzanie MSU UWM, Zarządzanie strategiczne

więcej podobnych podstron