Next: About this document ...
Formális nyelvek gyakorlat (2)
2005. szeptember 22., csütörtök
1. Adjunk determinisztikus véges automatát az alábbi nyelvhez:
osztható hárommal,
osztható kettővel.
2. Legyen
. A nyelv szavaira a következő két dolog igaz:
összesen páratlan sok karakter van bennük
után közvetlenül nem jöhet , után , után .
Determinisztikus véges automata kell erre a nyelvre.
3. Tegyük determinisztikussá az alábbi automatát!!
4. Adjunk (jobb- és bal-)reguláris nyelvtant a 3. feladat automatájához!
5. Legyen
. A jelsorozatokat tekintsük mint bináris számokat.
Adjunk automatát, amely pont a hárommal osztható számokat fogadja el!
Vegyük figyelembe, hogy szám 0-val nem kezdődik, kivéve ha az maga a 0.
6.
Determinizálni kell ezt:
7. Készíts olyan véges automatát, amely a tizedestört alakban felírt
racionális számokat fogadja el.
Pontosabban az elfogadandó szám vagy tizedespont nélküli egész szám
(pl. 123), vagy tartalmaz tizedespontot. Az utóbbi esetben azt is el kell
fogadni, ha az egészrész vagy a törtrész hiányzik, de persze legfeljebb az
egyik hiányozhat (pl. helyes az 123.456 vagy az 123. vagy a
.456 is, de nem fogadható el ha a bemenet csak egyetlen pontból áll.).
Megköveteljük továbbá azt is, hogy az egészrész ne kezdődjön felesleges 0-kal
(de pl. a 0.456 helyes).
8. Adjunk véges automatát
(a) az üres nyelvre, azaz ,
(b) a csak az -t tartalmazó nyelvre, azaz
.
9. Adjunk determinisztikus véges automatát a következő nyelvre:
létezik két -ben, melyek között
néggyel osztható számú egyes áll.
10. Determinisztikus véges automata kéretik:
-ben jobbról a 3. betű b
11. Készítsünk véges automatát, ami
ugyanazt a nyelvet fogadja el, mint amit az alábbi jobbreguláris
nyelvtan generál:
12. Készítsünk véges automatát, ami
ugyanazt a nyelvet fogadja el, mint amit az alábbi balreguláris
nyelvtan generál:
13. A 2. része nehéz
(a)
Adjunk állapotú nem determinisztikus VA-t az
nyelvhez!
(b) Mutassuk meg, hogy minden DVA, ami elfogadja ezt a nyelvet
legalább állapotú!
Next: About this document ...
Csima Judit
2005-09-22