zerowka

Zad 1

Automat ze stosem ???? pierwszy raz widzę ;D

Zad 2

Dana gramatyka G=<{S,A,B,0,1},{0,1},P,S> O regułach produkcji:

S->1A |1B

A->1S

B->0A|1S|lambda

Narysować wykres deterministycznej i wyznaczyć reguły produkcji.

S0->1S1

S1->0S2|1S0|lambda

S2->1S0

Zad 3

Jaki język generuje Gramatyka:

S->WR|Sww

W->w

R->Tr|lambda

T->t|Tr

L={w(tr^kr+lambda)(ww)ⁿ ,n=0,1… ,k=0,1…}

Zad 4

a)Narysować graf i

b)podać wzór chyba na wyrażenie chyba to się nazywało

Dane były: L{wƐ{a,b}*| zaczyna się wyraz czy słowo od dwóch liter „b” a kończy dwiema „a”

1. W=|bb(a+b)*aa|

Zad 5

Dany język skończony wyznaczyć gramatykę bezkontekstową i wyrażenie:

L={aba,aaa,bbabb,ababab,baaabbb,aabbaa}

Gramatyka:

S-> aba | aaa | bbabb | ababab | baaabbb |aabbaa

G=<{S,a,b},{a,b},P,S>

Wyrażenie:

W=| aba + aaa + bbabb + ababab + baaabbb +aabbaa |