Digitaalitekniikan laboratorio

TKK:AFT.055/R. Heinonen 20.5.95

Tik-79.151 AUTOMAATIT JA FORMAALIT KIELET

Tentti 23.5.95

Kirjoita jokaiseen paperiin

- nimi, osasto, vsk

- opintokirjan numero

- Autom. ja form. kielet tentti 23.5.95

Huom! Tentissä saa olla mukana oppikirjat tai vastaavat opetusmonisteet (sisältäen myös kurssin alussa jaetun monisteen kielten määrittelymenetelmistä). Mukana ei siis saa olla esim. harjoitustehtäviä, tenttiinlukuohjeita tms.

1. Tee redusoitu kielioppi, joka on ekvivalentti kieliopin G = (V, , P, S) kanssa.

V= {S, A, B, C, a, b}

= {a, b}

P: S aS A C

A a

B aa

C aCb

2. Muunna kielioppi G = (V, , P, S) Chomskyn normaalimuotoon.

V = {S, A, B, a, b}

= {a, b, c}

P: S abAB

A bAB

B BAa A

3. Muunna kielioppi G = (V, , P, S) Greibachin normaalimuotoon.

V = {A1, A2, a, b}

= {a, b}

P: A2 A1A2 b

A1 A2A2 a

4. Laadi 0L systeemi, joka generoi kielen L.

L = {ancbn n > 0}

5. Esitä lyhyt (1-2 s) jäsennelty kuvaus (sanallisesti ja kaavioita) formaalien kielten koko alueesta (kielten määrittely periaatteet ja menetelmät sekä näiden generoimat kieliperheet).