Nyelvek, nyelvtanok megadasa. Formalis nyelvek osztalyozasa. Chomsky-féle hierarchia.

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

G₁:= , , <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.:

G₂= < , , 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 aⁱ bⁱ 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ó: w_n levezethető w -ből G nyelvtan szerint, ha w w_n-1 szavak w w

G G

w w w_n-1 w_n

Jelölés: G

w w_n

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(G₁) =            L(G₂) =

Példa: Természetes számok felírása:

G₃ = < , , 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: A₀ azon számok, melyek 3-mal osztva 0-t adnak maradékul, stb )

G = < , , A₀, P >

P:         A₀ 0 | 3 | 6 | 9 | 3A₀ | 6A₀ | 9A₀ | 2A₁ | 5A₁ | 8A₁ | 1A₂ | 4A₂ | 7A₂

A₁ 1 | 4 | 7 | 1A₀ | 4A₀ | 7A₀ | 0A₁ | 3A₁ | 6A₁ | 8A₁ | 2A₂ | 5A₂ | 8A₂ |

A₂ 2 | 5 | 8 | 2A₀ | 5A₀ | 8A₀ | 1A₁ | 4A₁ | 7A₁ | 0A₂ | 3A₂ | 6A₂ | 9A₂ |

Példa: osztható 3-mal. Levezethető-e ?

A₀ 8 A₁ 98 A₁ 893 A₁ 8931 A₀ 89317 A₂

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: G₄ = < , , 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(G₄) =

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: G₅ = < , , S , P >

P:         S SS | 0S1 | 1S0 | 10 | 01

L(G₅) =

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 > =: G₆

P:         S 1A | e L(G₆) =

A 1B | 1

B 1A

Definíció: G_i :=

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)

G₀ Ê G₁ Ê G₂ Ê G₃

( Nem bizonyítjuk. )

Állítás: Ha L G_i , akkor L \ , L È G_i ( 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 G₂.

Á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'' G₃,

L'L'' G₃,

L'^* G₃.