online kép - Fájl  tubefájl feltöltés file feltöltés - adja hozzá a fájlokat onlinefedezze fel a legújabb online dokumentumokKapcsolat
  
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
  

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

számítógépes

Fájl küldése e-mail



egyéb tételek

 
Szamítógép halózatok előnyei
Az operaciós rendszer
IP labor A ping parancs végrehajtasi üzeneteinek elfogasa
Az operaciós rendszerek illesztése
Az Excel alapjai
Fajlkezelés, fajlok szerkezete, megnyitasa, írasa, olvasasa, egyéb fajlkezelõ utasítasok. Tipizalt és szövegfajlok.
A DOS unit fontosabb beépített konstansai, függvényei, eljarasai; hasznalata
Feladatok
Függelék
Az oracle sql
 
 

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: 841