614372770

9. Zaprojektować deterministyczne automaty rozpoznające słowa kluczowe:

(a)    while,

(b)    for,

(c)    begin,

(d)    program.

10.    Zaprojektować niedeterministyczne automaty rozpoznające słowa kluczowe:

(a)    while.

(b)    for,

(c)    begin,

(d)    program.

11.    Zaprojektować jeden deterministyczny automat rozpoznający słowa kluczowe:

(a)    while,

(b)    for,

(c)    begin,

(d)    program.

12.    Zaprojektować jeden niedeterministyczny automat rozpoznający słowa kluczowe:

(a)    while,

(b)    for,

(c)    begin,

(d)    program.

13.    Pokazać, dlaczego automat o następującym diagramie

który rozpoznaje słowa którego N-tym symbolem od końca jest jedynka, nie ma równoważnego deterministycznego automatu o liczbie stanów znacznie mniejszej niż 2ⁿ.

14.    Zdefiniować automaty skończone i deterministyczne które będą akceptować (rozpoznawać) języki opisywane przez poniższe wyrażenia regularne

(a)    (ao|6ó)*(a6|6a)*(aa|66)*

(b)    6(a6|6a)*(aa|66)*a

(c)    (a6|6a)^ł(66|aa)*(a6|6o)*

(d)    a(aa|W>)*(a6|6a)*6

15.    Zbudować deterministyczny automat skończony akceptujący język nad alfabetem T = 0,1

(a)    będący zbiorem wszystkich łańcuchów zerojedynkowych z wyjątkiem łańcucha 0110,

(b)    będący zbiorem wszystkich łańcuchów zerojedynkowych nie zawierających łańcucha 1010,

(c)    będący zbiorem wszystkich łańcuchów zerojedynkowych zawierających co najwyżej jeden raz łańcuch

101.

17