1. feladat
A kétirányú veremautomata olyan, mint a sima egyirányú, csak
visszafelé is bír lépkedni. Akkor fogad el, ha végigolvassa a szót és
elfogadó állapotba kerül. Vajon erősebb-e, mint a sima veremautomata?
(Segítség: az anbn
cn nyelv nem CF nyelv.)
|
2. feladat
Mit generálnak az alábbi nyelvtanok? Egyértelműk-e a nyelvtanok?
- S -> aSb | epszilon
- S -> SaSb | epszilon
- S -> SaSbS | epszilon
- S -> SaSbSa | epszilon
|
3. feladat
Környezetfüggetlenek-e az alábbi nyelvek?
(Szigma={a,b,c})
- Az a-k száma megegyezik mind a b-k, mind a
c-k számával.
- Az ab és ba minirészsorozatok száma azonos.
- L={aibicj
| i,j >= 1, i != j}
|
4. feladat
Készítsünk veremautomatát, mely az alábbi nyelveket fogadja el!
- {aibjck
| i+k=j, i,j,k >= 0}
- {ambn | 1 <= m <= n <= 2m}
- A mondatban másfélszer annyi a van, mint b.
|
5. feladat
Tervezz automatát azon Szigma={a,b} feletti nyelvhez,
melynek szavaiban a magányos b-k száma meghaladja az egynél
hosszabb homogén a sorozatok számát!
|
6. feladat
Csak egy additív és egy multiplikatív operátort feltételezve készíts
nyelvtant aritmetikai kifejezések posztfix jelöléssel történő
leírására!
Mutasd meg, hogy egyetlen nemterminális alkalmazása is egyértelmű
nyelvtant eredményez!
|
7. feladat
Adottak az alábbi nyelvek (i,j >= 0):
- ai+jbicj
- aibi+jcj
- aibjci+j
Ezek környezetfüggetlen nyelvek, amit igazolj azzal, hogy készíts rájuk CF
nyelvtant. Általában két környezetfüggetlen nyelv metszete nem
környezetfüggetlen. Vizsgáld meg a három páronkénti metszetet abból a
szempontból, vajon ezek is kilépnek-e a CF nyelvek köréből!
|
8. feladat
Készítsünk mind a két, könyvben leírt módszerrel
- a prefix, illetve
- az infix
aritmetikát generáló nyelvtanból veremautomatákat!
|
|