Digitaalitekniikan laboratorio
AFT.054/R. Heinonen 20.5.1994
Tik-79.151 AUTOMAATIT JA FORMAALIT KIELET
Kirjoita jokaiseen paperiin
- nimi, osasto, vsk
- opintokirjan numero
- Autom. ja form. kielet tentti 5/94
Huom! Tentissä saa olla mukana oppikirjat tai vastaavat opetusmonisteet (sisältäen myös esim. kurssin alussa jaetun monisteen kielten määritteiymenetelmistä). 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 Ac
B aa aB
C aCb
2. Muunna kielioppi G = (V, , P, S) Chomskyn normaalimuotoon.
V = {S, A, B, a, b}
= {a, b, c}
P: S aSS abAB
A bAB
B BAa A
3. Muunna kielioppi G = (V, , P, S) Greibachin normaalimuotoon.
V = {A1, A2, a, b}
Z = {a, b}
P: A2 A1A2 b
A1 A2A2 a
4. Millaisen kielen generoi 0L systeemi
<{a, b}, {a a2, b ab}, ab>
5. Sovella graafiproduktiota p1 graafiin G. Graafit ovat seuraavalla sivulla. Morfismit on osoitettu solmujen numeroinnilla (solmut 1, 1' ja l" vastaavat toisiaan jne.). esitä lopputuloksen lisäksi myös väligraafi H, jonka liimaus B1:n kanssa K:n kautta tuottaa G:n.
TEKNILLINEN KORKEAKOULU 2 (2)
Digitaalitekniikan laboratorio
AFT.054/R. Heinonen 20.5.1994
Produktio P1
Graafi G