kategória | ||||||||||
|
||||||||||
|
||
Nyelvek, nyelvtanok megadása. Formális nyelvek osztályozása. Chomsky-féle hierarchia.
FORMÁLIS NYELVEK -VÉGES AUTOMATÁK
BNF kifejezés helyes Þ szintaxisfája Þ le lehet vezetni.
Cél: Pontosítani a levezetés fogalmát és módszereket adni a levezetések megkonstruálására.
Definíció: Formális nyelv:
Legyen T egy abc. L T* formális nyelv a T abc felett.
Nyelvek megadása:
- Véges nyelvek: elemeinek megadásával
Pl.: L =
- Végtelen nyelvek:
- Halmaz megadásával:
Pl.: L =
- Szabályok segítségével: ( BNF általánosítása )
FORMÁLIS NYELVEK GENERÁTORAI -GENERATÍV GRAMMATIKÁK
Definíció: G generatív grammatika a következő rendezett négyes:
G = < T, N, S, P >, ahol
T: véges abc, terminális jelek halmaza
N: véges halmaz - nemterminális jelek. T N = 0
S N kezdőjel, vagy kiinduló szimbólum
P: helyettesítési szabályok véges halmaza
Szabály: p q alakú, ahol
p ( T È N )* Ù p-ben van nyelvtani jel
q ( T È N )+
Példa: Azonosító:
T N S
G1:= , , <azonosító> , P }
P: <azonosító> <betű>
<azonosító> <betű><azonvég>
<azonosító> <betű> | <szjegy> | <betű><azonvég> | <szjegy><azonvég>
<betű> A | B | ...| Z
<szjegy>
Példa 2.:
G2= < , , S, P >
P: S aSb
S ab
( Rövid jelölés: S aSb | ab )
Megjegyzés: Egy levezetés:
S aSb aaSbb aaabbb
Nyelv: A kezdőszimbólumból levezethető terminális jelsorozatok összessége.
Példában: Olyan szavak, melyek ai bi alakúak i³
Definíció: ! G = < T, N, S, P > grammatika.
m közvetlenül levezethető h-ból, ha m h ( TÈN)* és g d ( TÈN)*
és a b P szabály h gad m gbd
Jelölés:
G
h |--- m G
Definíció: wn levezethető w -ből G nyelvtan szerint, ha w wn-1 szavak w w
G G
w w wn-1 wn
Jelölés: G
w wn
Megjegyzés: n a levezetés hossza.
Definíció: G = < T, N, S, P > nyelvtan generálja az a T* szót, ha: S |=== a
Definíció: G = < T, N, S, P > grammatika generálja az L T* nyelvet, ha:
G
L =
Jelölés: L(G)
Definíció: G' és G'' nyelvtanok ekvivalensek, ha L(G') = L(G'')
Példa: L(G1) = L(G2) =
Példa: Természetes számok felírása:
G3 = < , , s , P >
P: s s0 | s1 | ... | s9 | 1 | 2 | ... |9
Példa: 3-mal osztható természetes számok:
( -009, 000, stb is a nyelvhez tartoznak )
- nem terminális jelek: 3-mal való osztás maradékosztályai: A0 azon számok, melyek 3-mal osztva 0-t adnak maradékul, stb )
G = < , , A0, P >
P: A0 0 | 3 | 6 | 9 | 3A0 | 6A0 | 9A0 | 2A1 | 5A1 | 8A1 | 1A2 | 4A2 | 7A2
A1 1 | 4 | 7 | 1A0 | 4A0 | 7A0 | 0A1 | 3A1 | 6A1 | 8A1 | 2A2 | 5A2 | 8A2 |
A2 2 | 5 | 8 | 2A0 | 5A0 | 8A0 | 1A1 | 4A1 | 7A1 | 0A2 | 3A2 | 6A2 | 9A2 |
Példa: osztható 3-mal. Levezethető-e ?
A0 8 A1 98 A1 893 A1 8931 A0 89317 A2
NYELVEK OSZTÁLYOZÁSA( Chomsky-féle hierarchia )
Definíció: 0. típusú nyelvtan.
Szabályokra nincs megkötés, azaz a szabályok alakja: a A b w, ahol
a b w ( TÈ N )* és A N
Definíció: G = < T,N,S,P > 1-es típusú nyelvtan ha a szabályok alakja:
aAb awb , ahol
a b w ( TÈ N )* és A N , w ¹ e
( Tehát A csak bizonyos környezetben helyettesíthető w-val. )
környezetfüggő nyelvek.
Megjegyzés: Azért, hogy az üres szót is levezethessük, megengedjük az S e szabályt, de ekkor S nem állhat szabály jobb oldalán. ( Így a jobb oldal soha nem rövidebb, mint a bal. )
Példa: G4 = < , , S , P >
P: S aSAC | abC
CA BA C jobb oldali környezete : A
BA BC A bal oldali környezete : B
BC AC B jobb oldali környezete : C
bA bb A bal oldali környezete : b
C c
Belátható: L(G4) =
Definíció: G = < T,N,S,P > 2-es típusú nyelvtan ha a szabályok alakja:
A w , ahol A N és w ( TÈ N )* , w ¹ e
környezetfüggetlen nyelvtan.
Megjegyzés: G tartalmazhatja az S e szabályt, S ekkor nem állhat szabály jobb oldalán.
Példa: G5 = < , , S , P >
P: S SS | 0S1 | 1S0 | 10 | 01
L(G5) =
Definíció: G 3-as típusú, vagy reguláris nyelvtan, ha a szabályok alakja:
A aB , vagy A a , ahol A.B N , a T.
Megjegyzés: Ugyanaz, mint fent.
Példa: < , , S , P > =: G6
P: S 1A | e L(G6) =
A 1B | 1
B 1A
Definíció: Gi :=
Definíció: L reguláris nyelv (környezetfüggő, stb.), ha L G , azaz G reguláris nyelvtan L = L(G).
Tétel: (Chomsky-féle hierarchia)
G0 Ê G1 Ê G2 Ê G3
( Nem bizonyítjuk. )
Állítás: Ha L Gi , akkor L \ , L È Gi ( i = 1,1,2,3 )
Állítás: véges nyelv leírható reguláris grammatikával.
Példa: Egy programozási nyelv alapszimbólumai leírhatók reguláris grammatikával lexikális analízis
Megjegyzés: Programozási nyelvek lényegi szintaxisának megadására: L G2.
Állítás: Tetszőleges végtelen nyelv nem írható le nyelvtannal.
Reguláris nyelvek tulajdonságai:
! L' és L'' reguláris nyelvek.
Ekkor: L' È L'' G3,
L'L'' G3,
L'* G3.
Találat: 1372