I

Automaty i Gramatyki

(kolokwium poprawkowe)

17 n 2010

/,,//

pj*y₄.

Imię i nazwisko.................-..........................................U.-,.. Nr indeksu:.

1. Podaj wzorzec opisujący język złożony ze słów nad alfabetem {a, 6, c}, w których litery c i b nie sąsiadują ze sobą.

2. Podaj automat skończony akceptujący język złożony ze słów nad alfabetem (<t,6,c}, w których między każdymi dwiema kolejnymi literami c występuje przynajmniej jedna litera o i

prtynąjmnlęj jedna litera 6.

l>. C

3. Zdeterminizuj następujący automat ni ed eter minia tyczny (pomijamy stany nieosiągalne):

a P    ' Vi/Xi Ł H    ^^rv—*

i

1 2 2,3 1,2 1.2 1

7 $ m fZ 12 f ? $ ^ 7 ⁴²^ *²

4. Podaj gramatykę bezkontekstową generującą język złożony ze słów postaci (a^c* : | ^ * 3k A ,/' > l}. Narysuj drzewo wyprowadzenia słowa aaabbc w otrzymanej gramatyk.

i e    Hafn

M \ I

“- •*««i£

i -■> « ŁM.

*    6 X r t

I

a £g u