|
Formális nyelvek gyakorlat (4)
2001. március 6., kedd
1. Az alábbi táblázattal adott egy véges automata, melynek 12 állapota van és
input ábécéje az halmaz. Kezdőállapot a ,
elfogadó állapotok a és a .
Minimalizáld az automatát!
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
a |
3 |
9 |
11 |
2 |
11 |
6 |
8 |
10 |
1 |
4 |
8 |
4 |
b |
5 |
4 |
8 |
11 |
4 |
11 |
4 |
4 |
7 |
0 |
4 |
11 |
2. Készítsünk minimálautomatát az alábbi nyelvhez:
3. Álljon az nyelv azon szavaiból, melyek
ha -ra végződnek, akkor nen tartalmaznak részszót, és
ha -re végződnek, akkor nem tartalmaznak részszót.
Készíts minimálautomatát ehhez a nyelvhez!
4. Adjunk minimálautomatát az alábbi nyelvtan
által generált nyelvhez
5. Legyen
és álljon az nyelv azokból
a legalább 3 hosszúságú szavakból, melyekben minden három
hosszú részszó legalább 2 darab betűt tartalmaz.
Készíts minimálautomatát az nyelvhez!
6. Az nyelv szavaiban a szavak nem ugyanazzal a betűvel kezdődnek,
mint amivel végződnek, így páros számú homogén
részsorozat van minden szóban.
Párosítva ezeket (az elsőt a másodikkal, a harmadikat a negyedikkel,
stb.), minden pár hossza páratlan, tehát a pár
egyik tagja páros a másik meg páratlan. Adjunk az nyelvhez
minimálautomatát!
7. Az nyelv mondatainak hossza osztható
hárommal, az üres szó nincs a nyelvben.
Ezek szerint a nyelv egy tetszőleges szavának
karaktereit hármasával csoportokra oszthatjuk (az elejéről kezdve).
Minden csoportban valamelyik karakter legalább kétszer előfordul.
A nyelvbe azon szavak tartoznak, melyekben ez
a többségi karakter a szomszédos csoportokban egymástól különbözik.
Szerkesszen minimálautomatát a fenti nyelvre!
|