online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

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
   
kategória
 

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

 
 
 
 













































 
 

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

számítógépes

Fájl küldése e-mail Esszé Projekt


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> ® 0 | 1 | ... | 9

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³1.

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ő w1-ből G nyelvtan szerint, ha w1,...wn-1 szavak ® w1 |--- w2,

       G                      G

w2 |--- w3, ... , wn-1 |--- wn .

Jelölés:                   G

                        w1 |=== 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: 893172 ® osztható 3-mal. Levezethető-e ?

A0 ® 8 A1 ® 98 A1 ® 893 A1 ® 8931 A0 ® 89317 A2 ® 893172

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