1. feladat
Adjuk meg automatával és nyelvtannal: a nyelv azon a és
b karaktersorozatokból álló jelsorozatokat tartalmazza, ahol
legalább két a vagy legalább két b karakter egymás után
áll. (Szigma={a,b})
|
2. feladat
A nyelv azon jelsorozatok összessége, melyek aaa-val
kezdődnek. (Szigma={a,b}) Adjunk meg egy automatát,
amely az előbb megadott nyelvet fogadja el!
|
3. feladat
Szigma={a,b} A nyelv azon jelsorozatok összessége,
amelyekben a mondat hossza páros (tehát nulla hosszú is lehet). Add
meg az automatáját és egy nyelvtanát!
|
4. feladat
Determinizáljuk az alábbi automatát! Milyen nyelvet generál?
|
5. feladat
Determinizáljuk az alábbi automatát! Milyen nyelvet generál?
|
6. feladat
Szigma={0,1} A belőlük alkotható jelsorozatokat, mint
egész számokat fölfogva, a nyelv legyen a hárommal osztható
(3=011) számok összessége.
|
7. feladat
Egy nyelv alfabetája Szigma={0,1,2,3}. A
jelsorozatot fogjuk fel, mint egy szám tetrális reprezentációját
(négyes számrendszer, és az automata balról (nagyobb helyiérték)
jobbra (kisebb helyiérték) olvassa). Készíts automatát, amely az
öttel osztható számokat fogadja el!
|
8. feladat
Egy nyelv karakterkészlete Szigma={a,b,c}. A
nyelv mondataira a következő megállapítások érvényesek:
- Minden mondatban mindhárom karakter előfordul.
- Amennyiben két szomszédos karakter nem azonos, akkor a
karakter után csak b, b után csak c, c
karakter után csak a karakter következhet.
Készíts automatát a fent definiált nyelvre!
|
9. feladat
Szigma={a,b,c} Készíts automatát az alábbi nyelvre!
- a után nem jöhet b, b után nem jöhet
c közvetlenül.
- Összesen páratlan karakter van egy mondatban.
- Valamelyik fajtából páros sok van.
|
10. feladat
- Homogén részsorozat az a nem üres karaktersorozat,
amelynek karakterei azonosak.
- Egy homogén részsorozat teljes, ha az nem terjeszthető
ki, vagyis határoló karakterei - ha vannak - különböznek a sorozatot
alkotó karakterektől.
- Egy teljes homogén részsorozat páratlan
ill. páros, ha a sorozatot alkotó karakterek száma páratlan
ill. páros.
Legyen Szigma={a,b}. Az L1 illetve
L2 nyelv mondatai tartalmaznak legalább egy - L1
esetben páratlan, L2 esetben páros - teljes homogén
részsorozatot. Add meg a két nyelv automatáját!
|
11. feladat
Készítsünk bal- ill. jobbreguláris nyelvtanokat a 4. feladat
determinizált automatájából! (Természetesen a két nyelvtannak ugyanazt a
nyelvet kell generálnia, mint amit az automata elfogad.)
|
12. feladat
Készítsünk véges automatát, amely ugyanazt a nyelvet fogadja el, mint
amit az alábbi jobbreguláris nyelvtan generál:
- S -> aS | bB | b
- A -> aA | a | bC
- B -> bB | b | aA | a
- C -> bC | aS
|
13. feladat
Készítsünk véges automatát, amely ugyanazt a nyelvet fogadja el, mint
amit az alábbi balreguláris nyelvtan generál:
- S -> Sb | Aa | a
- A -> Sa | Bb
- B -> Ba | Bb | epszilon
|