Formális nyelvek, automaták

Országok listájaHungaryNyíregyházi FőiskolaTermészettudományi Főiskolai KarProgramozó matematikusZáróvizsgaFormális nyelvek, automaták

16. Formális nyelvek
(alapfogalmak, mqveletek nyelvekkel, generatív nyelvtanok, Chomsky-féle nyelvosztályok, reguláris nyelvek, környezetfüggetlen nyelvek, automaták)
Alapfogalmak:
Ábécé: Def.: Legyen A véges nem üres halmaz, elemei szimbólumok, melyek külön-külön és csoportosítva is különböznek egymástól.
Szó: Def.: A feletti szó, A beli szimbólumok véges sorozata. Üres sorozat: µ, üres szónak nevezzük.
Szó hossza: a szót alakotó jelek száma. Jele: l(v)
Üres szó: µ, l(µ)=0
Nyelv (A ábécé felett): A feletti szavak tetszQleges halmaza.
Teljes nyelv: A ábécé feletti összes szó, beleértve µ-t is. Jele: A*
Szavak azonossága: v=w ha v,w A; v=a1, & an; w=b1, & bn; l(v) = l(w); minden i=1& n-re fennáll, hogy ai = bi.

A formális nyelvek egy lehetséges mqvelete a konkatenáció, és µ az egységeleme. A teljes nyelvbQl (A*) a konkatenáció nem vezet ki, tehát algebrai struktórát alkot. Az összefqzés asszociatív, tehát félcsoport, és van egységeleme. ( A teljes nyelv egységelemes félcsoport.

Mqveletek nyelvekkel:

µ mentesítés: Lehetnek olyan szabályok, hogy nem terminális elembQl µ lesz. Leírjuk mégegyszer az összes szabályt, és hozzáképezzük azokat amibQl hiányoznak ezek a nem terminális elemek.
S ( AB|µ|SAa
A ( CAaB|µ|bb
B ( ACB|µ|bBB
C ( CA|a S (AB|A|B|SAa|Sa|Aa|a
A (CAaB|CaB|CAa|Ca|bb
B ( ACB|CB|AC|C|bBB|bB|b
C ( CA|C|a Átnevezés, egyszeres szabály megszüntetése: A ( B típusú szabályok megszüntetése úgy, hogy a B helyére beírjuk a B összes szabályát.

Generatív nyelvtan egy olyan lehetQség amivel nyelveket adhatunk meg. A nyelv a szavak és mondatok halmaza, a nyelvtan pedig a szabályok összessége. 4 dologgal lehet teljesen meghatározni a nyelvtant: G(", N ,M, SZ) vagy (VT, Vn, S, P).
": terminális elemek halmaza, azaz a nyelv ábécéje (kis betqvel jelöljük: a, b, c)
N: nem terminális elemek halmaza (nagy betqk: A, B, C)
M: N, mondatszimbólum (jele: M vagy S)
SZ: leveztési szabályok halamza A+ × A*  EMBED Equation.3 SZ
Az A halmaz a terminális és nem terminális elemek halmaza (A = " U N). EzekbQl készített összes jelsorozat az A*. Ha A*-ból kivesszük µ-t, A+-t kapjuk. E kettQ Descartes szorzatának egy részhalmaza lesz a szabály.

Def.: LevezethetQség: v-bQl egy lépéssel levezethetQ w, ha v=±²³, w=±´³ és (²´) SZ. A v ²-ját ki tudjuk cserélni ´-ra.
Def.: A w jlsorozat mondata a G által generált nyelvnek (w G) amennyiben csupa terminálisból áll, és levezethetQ véges sok lépésben M-bQl SZ alapján.

Chomsky-féle nyelvosztályok:
A generatív nyelveket tehát grammatikák segítségével jellemezhetjük. A grammatikákat meghatározó helyettesítési sabályok bonyolultsága alapján Chomsky a nyelveket osztályokba sorolta.
Chomsky 4 nyelvosztályt definiált. Ezeket számokkal jelölte, így van 0-s, 1-es, 2-es, 3-as nyelvosztály. Az osztály sorszámának növekedésével egyre szigorúbbak a megkötések a szabályok alakjára vonatkozóan.

3-as nyelvosztály (reguláris): A helyettesítési szabály bal oldala mindig egyetlen nem terminális elem, a jobb oldala pedig egyetlen terminális elem, vagy jobbreguláris nyelvtan esetén egy terminális és egy nem terminális, balreguláris nyelvtannál egy nem terminális és egy terminális elem.
A ( a
A ( aB – jobbreguláris
A ( Ba – balreguláris

2-es nyelvosztály (környezetfüggetlen): A helyettesítési szabály bal oldala mindig egyetlen nem terminális elem, a jobb oldala pedig*L N h j t ’ ” Z
\
h
n
~
€
œ
ž
0
D
”
–
¦
¾
È
Ì
Î
î
ð
:

R

V

X

¾

À

Ä

æ







"
,
.
8
:
–
˜

¢
¨
n p ìåÞ×åËÃËûÃËÃËÃËï§Ã¯§¯§¯§¯§¯§¯§¯§¯§¯§›§›§›§›§›§›§“‡“hJBåhœ{6OJQJ hœ{OJQJhJBåhJBåH*OJQJ hJBåOJQJhJBåhJBå6OJQJ h‡-àOJQJ hN]}OJQJhN]}hN]}6OJQJ

hèA†hN]}

hèA†h%3-

hèA†h+%hèA†h+B*CJOJQJaJph6_‘5*N j h
0
–
¾
:

Ä

¦
¨
ÈÊöúpŠ¦ÂÔ,^tôìçââââââââââçââÙÙÙÙÎÎÎÎ
¤x$Ifgd

D $Ifgd8igd+gdèA† $a$gdèA†
$d ¤xgd@

"tvÈÊöøúþ‚„nptv~€Žœžª¬¶õíßíÑÊ»³£—€umbTbEbTbEbTbh

Dh8iCJ$OJQJaJ$ jàðh

Dh8iOJQJ h

Dh8iOJQJ h[o—OJQJ h8ih8iOJQJh8ih8iCJ$OJQJaJ$ h8iOJQJh

Dh8i>*OJQJ-h

Dh8i>*CJ$OJQJaJ$ hJBåOJQJjh[o—h[o—OJQJU

hèA†hJBåh[o—>*B*
OJQJph€ jàðhœ{hœ{OJQJ hœ{OJQJ h+hœ{OJQJ¶¸ÆÈØÚ&*,02bdtvÒÔ~‚¦Ò @BHJZ\8ñæØæØæØæÍæÍ¿Í¿Íæ·¿·¯—‡{‡{‡‡o‡`U hlËhlËOJQJjhlËhlËOJQJUhlËhlËH*OJQJhlËhlËH*OJQJ hlËOJQJ h[o—OJQJ/hèA†h[o—5B*CJOJPJQJ\aJphO½ h8iOJQJ h

DOJQJ jàðh

Dh

DOJQJ h

Dh

DOJQJ jàðh

Dh8iOJQJ h

Dh8iOJQJh

Dh8iCJ$OJQJaJ$!tv€‚\pÀDðòä P„zgdèA†gd+{kd’$$If–FÖÖ0”ÿ’#þþ
t Ö0 ö6öÖÿÿÖÿÿÖÿÿÖÿÿ4Ö4Ö
laöyt

D 8:<>BDÆÈ\^î𐒠PÈ./0ACLMORSUéØɾ¶®§®›®¶®®ˆˆyˆqeqMqyqyq/hèA†h»mL5B*CJOJPJQJ\aJphO½h»mLh4-5OJQJ h»mLOJQJ h4-OJQJ

hèA†hñï hñïOJQJ h»=h»=OJQJhlËh»=H*OJQJ

h»=h»= h»=OJQJ hlËOJQJ hlËhlËOJQJjhlËhlËOJQJU!jŽhlËhlËEHüÿOJQJU+j§UJ
hlËhlËCJ OJQJUVaJ P`/0SYp†‡ž0ª0¬0¤2¦2À3Â3Ö3´45N5 6J6ê6þ6<7´7 8÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷ò÷÷÷÷÷÷÷ççç
$
&
Fa$gd`

ògdèA† $a$gdñïUV[\rs‡˜š¬ 0¢0¤0¬0Î0ö0ü0þ01122¢2¤2¦2Æ2À3Ô3Ö34&466>6@6B6D6¤6òêòêòêÞêÆêÄêòêÞê¼®¼®¼®¼ê¦š¼’¼Š~ŠrŠrŠkŠ

h§ Õh§ Õh§ Õh§ ÕH*OJQJhÇãh§ Õ5OJQJ h§ ÕOJQJ hèA†OJQJhRGˆhRGˆ5OJQJ h4-OJQJ jàðhRGˆhRGˆOJQJ hRGˆOJQJU/hèA†h»mL5B*CJOJPJQJ\aJphO½h»mLh»mL5OJQJ h»mLOJQJ jàðh»mLh»mLOJQJ& tetszQleges, mind terminális, mind nem terminális szimbólumokat tartalmazhat.
A ( ±

1-es nyelvosztály (környezetfüggQ): ²A³ ( ²±³ azaz az A ( ± szabály csakis a ²-³ környezetben alkalmazható. Vagy a helyettesítési szabály jobb oldala nem lehet rövidebb a bal oldalnál ( nem csökkenQ nyelvek. Ez a két definíció ugyanazt a halmazt adja.

0-s nyelvosztály: Nincs megkötés. (Csak ami minden grammatikánál: a bal oldalnak tartalmaznia kell legalább egy nem terminális szimbólumot.)

Automaták
A reguláris nyelvekhez a véges automaták tartoznak. Ezek a legegyszerqbbek, nincs memóriája, csak olvasni tud.
Q: az automata állapotainak véges halmaza
": az elemzendQ jelsorozat ábécéje
´: az automata mozgási szabályainak véges halmaza (mint nyelvtanoknál a helyettesítési szabály)
q0: az induló állapot. q0 Q
F: elfogadó állapotok halmaza. Az összes állapotok halmazának rész halamza FQ.
Mqködése:
Az automata q0 állapotban van.
A szalagon az input szó betqi vannak balról jobbra felírva.
Az olvasófej a szó legbaloldalibb celláján áll.
Ciklus
Beolvassa az olvasófej alatti cellában lévQ jelet
Ezen jel és az aktuális állapot függvényében a ´ szerinti állapotba kerül, (ha nincs megfelelQ szabály a szót elutasítja, és az automata leáll)
Az olvasófejet lépteti balra
Az olvasófej megáll, ha az automata lelép a szalagról (beolvasta a szót).
Ha az automata végállapotba került, akkor elfogadta az input szót.

Determinisztikus automata: Ha minden álapot-karakter párhoz legfeljebb 1 mozgási szabály tartozik. (ellentéte a nemdeterminisztikus automata).
Teljesen specifikált automata: minden állapot-karakter párhoz létezik mozgási szabály.
Minimálautomata: determinisztikus és teljesen specifikált automata minimális állapotszámmal. Minden nyelvhez egyetlen ilyen tartozik.

A környezetfüggetlen nyelvekhez a veremautomaták tartoznak.
Q: az automata állapotainak véges halmaza
": az elemzendQ jelsorozat ábécéje
“: a verem ábécéje, vagyis azon szimbólumok véges halmaza, amelyek a veremben szerepelhetnek
´: az automata mozgási szabályainak véges halmaza (mint nyelvtanoknál a helyettesítési szabály)
q0: az automata kezdQ állapota. q0 Q
Z0: a memória kezdeti tartalma (Z0 “)
F: elfogadó állapotok halmaza. Az összes állapotok halmazának rész halamza FQ.

A környezet függQ nyelvekhez a lineárisan korlátolt automaták osztálya tartozik.
A mondatszerkezetq nyelvekhez a Turing-gép automaták osztálya.









 PAGE \* MERGEFORMAT 1

Hasonló témájú dokumentumok

Hozzászólások

11.05-2 2008_12_17 26 7. állattan ásványtan barta ferenc csáth diszkrét matematika dm doc éghajlat éptöri épülettervezés 4 ergonómia etika fazekas gábor gazdinfo géntech hallás informatika inverz és összetett függvény japán juhász kiselőadás kőzetek lophotrochozoa magánjog matek jegyzet mikroökonómia minden növények numerikus órai dia prácser tamás reklámelmélet és gyakorlat reneszánsz stratégia stratégiai menedzsment szociális jog természetvédelem topográfia tőkeelmélet vállalat gazdaságtan vésés villamos gépek villamosságtan vizes éh. kez. white zh