|
Általános és regulárisos feladatok
1. (i) Adjunk 0-s nyelvtant az alábbi nyelvhez:
nem alakú
**
(ii) Adjunk CF nyelvtant is hozzá.
*
2.
Mutassuk meg, hogy minden DVA, ami elfogadja a
nyelvet legalább állapotú, noha nemdeterminisztikus véges automata
már van állapottal is!
*
3.
Nyelvtan kell az
az -edik Fibonacci szám
nyelvre. (Nem baj, ha 0-s lesz a nyelvtan)
**
4.
Nyelvtan kell az prím szám
nyelvre. (Itt se baj, ha 0-s lesz a nyelvtan, sőt mar az is jó, ha
nagyjából el tudod mesélni, hogy hogyan működjön a nyelvtan, nem kell
rögtön szabályokra lebontva leírni.)
***
5.
Regulárisak-e az alábbi nyelvek?
-
-
Az egyik nem is csillagos, a másik meg **.
6.
Regulárisak-e a következő nyelvek?
-
**
-
az -edik Fibonacci-szám *
7.
Vigyázat, ez nem igaz!!!
Valamit elrontottam, nem ezt a példát akartam kitűzni. Így két feladat van:
(a) Miért nem igaz?
(b) Milyen plusz feltételekkel lehet igaz ez?
A feladat eredeti formájában:
Tegyük fel, hogy az nyelv reguláris, az nyelv pedig nem reguláris.
Igazoljuk, hogy ekkor sem reguláris!
**
8.
Legyen egy reguláris nyelv a ábécé felett.
.
Azaz -ben az -beli szavak első felei vannak. Reguláris-e
az nyelv?
** és fél *
9. Bizonyítsd be, hogy ha
és CF nyelv, akkor
reguláris is!
Most éppen én se tudom, hogyan megy, valószínűleg igen nehéz = ****
|