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
  
felso sarok kategória jobb felso sarok
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
bal also sarok   jobb also sarok
felso sarok   jobb felso sarok
 




































 
bal also sarok   jobb also sarok

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

számítógépes





felso sarok

egyéb tételek

jobb felso sarok
 
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
 
bal also sarok   jobb also sarok

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