2-2-gramatyki.pdf
(
103 KB
)
Pobierz
24735649 UNPDF
2.2. Gramatyki, wyprowadzenia
Gramatyka
Gramatyką
G
nazywamy czwórkę uporządkowaną
G = <N, T, P, Z>
gdzie:
N – zbiór symboli nieterminalnych,
T – zbiór symboli terminalnych,
P – zbiór produkcji, z których każda ma postać
α
β
Z
N – wyróżniony symbol początkowy (nieterminal)
przy czym
P
(N
T)
+
(N
T)
*
P = { α
β | α
(N
T)
+
, β
(N
T)
*
}
Wyprowadzalność
Słowo ψ jest wyprowadzalne bezpośrednio ze słowa ω w gramatyce
G
, co zapisujemy
ω
G
ψ
jeżeli:
ω = γαδ
ψ = γβδ
(α
β)
P
T)
*
Słowo ψ jest wyprowadzalne ze słowa ω w gramatyce
G
, co zapisujemy
ω
α, β, γ, δ, ψ, ω
(N
G
+
ψ
jeżeli istnieją φ
0
, φ
1
, ... ,φ
n
(N
T)
*
takie, że:
G
φ
i
dla i = 1, 2, ..., n
Sekwencję
φ
0
, φ
1
, ... ,φ
n
nazywamy wyprowadzeniem o długości
n
.
Definiujemy ponadto:
( ω
G
*
ψ )
( ω
G
+
ψ )
( ω = ψ )
G
*
są odpowiednio przechodnim oraz przechodnim i zwrotnym
domknięciem relacji bezpośredniej wyprowadzalności
G
+
oraz
G
. Jeżeli wiadomo, o jaką
gramatykę chodzi, pomijamy dolny indeks „G” w oznaczeniu tych relacji pisząc po prostu:
+
,
*
oraz
.
Język generowany przez gramatykę
Gramatyka jest jednym ze sposobów definiowania języka formalnego. Mając daną
gramatykę
G
oznaczamy przez
L(G)
zbiór wszystkich słów, które mogą być w tej
gramatyce wyprowadzone z symbolu początkowego
Z
. Zbiór ten nazywamy językiem
generowanym przez daną gramatykę.
φ
0
= ω
φ
n
= ψ
φ
i-1
Relacje
L(G) = { x
T
*
| Z
G
*
x }
T)
*
nazywamy
formą zdaniową
gramatyki
G
, jeśli można go
wyprowadzić z symbolu początkowego
Z
.
(N
G
*
x
Uwaga: terminu
słowo
używamy w rozumieniu łańcucha zbudowane wyłącznie z symboli
terminalnych
(N
T)
*
jest
formą zdaniową
Z
x
T
*
jest
słowem
Z
G
*
x
Hierarchia Chomsky’ego
Noam Chomsky zdefiniował cztery klasy gramatyk oraz cztery klasy języków formalnych.
Klasy te numerowane są od
0
do
3
.
Klasa 0
Gramatykę
G = <N, T, P, Z>
, w której produkcje mają postać
α
β
, gdzie
α
i
β
są
nazywamy
semi-gramatykami Thuego, gramatykami bez ograniczeń, gramatykami struktur frazowych,
gramatykami kombinatorycznymi
lub
gramatykami klasy „0”
.
Definicja gramatyk klasy „0”, jak widać, nie nakłada żadnych ograniczeń na postać produkcji
gramatyki w stosunku do ogólnej definicji gramatyki.
Języki generowane przez gramatyki tego typu noszą nazwę
języków rekurencyjnie
przeliczalnych
.
Przez
G
KOMB
oznaczymy klasę gramatyk kombinatorycznych, a przez
L
RP
klasę języków
rekurencyjnie przeliczalnych.
Fundamentalny problem, który będzie później naszym głównym przedmiotem
zainteresowania, mianowicie: „czy słowo
x
należy do języka generowanego przez daną
gramatykę”, jest nierozstrzygalny dla języków generowanych przez gramatyki
kombinatoryczne. Termin „problem” w uproszczeniu oznacza pytanie związane z jakimś
wystąpieniem pewnych obiektów z pewnych klas (u nas tymi obiektami są dowolne
gramatyki pewnego typu oraz dowolne słowa nad alfabetem definiowanym przez te
gramatyki, zaś wystąpieniem obiektu będzie konkretne słowo i konkretna gramatyka), na
które to pytania można udzielić odpowiedzi:
TAK
lub
NIE
. Termin „nierozstrzygalny” w
uproszczeniu znaczy tyle: „nie istnieje jednoznaczny deterministyczny algorytm, który dla
każdego wystąpienia danego problemu w skończonej liczbie kroków dałby odpowiedź
TAK
,
jeżeli poprawna odpowiedź na pytanie związane z wystąpieniem rozważanego problemu
brzmi
TAK
, oraz
NIE
, gdy poprawna odpowiedź brzmi
NIE
”. Termin „rozstrzygalny” w
uproszczeniu znaczy tyle: „istnieje jednoznaczny deterministyczny algorytm, który dla
każdego wystąpienia danego problemu w skończonej liczbie kroków dałby odpowiedź
TAK
,
jeżeli poprawna odpowiedź na pytanie związane z wystąpieniem rozważanego problemu
brzmi
TAK
, oraz
NIE
, gdy poprawna odpowiedź brzmi
NIE
”.
Problem: czy x
L(G) jest nierozstrzygalny dla G
G
KOMB
.
Forma zdaniowa
Łańcuch x
x
dowolnymi łańcuchami symboli tej gramatyki, przy czym
α
β
, gdzie
α
i
β
są
takimi łańcuchami symboli tej gramatyki, że łańcuch
β
jest przynajmniej tak długi jak
łańcuch
α
(|α|
, jeśli język
zawiera słowo puste, nazywamy
gramatykami kontekstowymi, gramatykami monotonicznym,
gramatykami nieskracającymi
lub
gramatykami klasy „1”
. Termin „kontekstowy” pochodzi
od tego, że dla każdej gramatyki monotonicznej można znaleźć równoważną jej (tzn.
generującą ten sam język) gramatykę, której produkcje mają postać
α
1
Aα
2
|β|)
oraz dodatkowo dopuszczona jest produkcja
Z
α
1
βα
2
gdzie
A
jest nieterminalem
(A
N)
, zaś
α
1
,
α
2
,
β
są dowolnymi łańcuchami symboli gramatyki, przy
. Produkcje o tej postaci pozwalają na zastąpienie nieterminala
A
łańcuchem
β
tylko w „lewostronnym kontekście”
α
1
i „prawostronnym kontekście”
α
2
.
Języki generowane przez gramatyki tego typu noszą nazwę
języków kontekstowych
.
Przez
G
K
oznaczymy klasę gramatyk kontekstowych, a przez
L
K
klasę języków
kontekstowych.
Problem: czy x
L(G) jest rozstrzygalny dla G
G
K
.
Ponadto:
G
K
G
KOMB
L
K
L
RP
Klasa 2
Gramatykę
G = <N, T, P, Z>
, w której produkcje mają postać
A
β
, gdzie
A
jest
N)
, zaś łańcuch
β
jest dowolnym łańcuchem symboli tej gramatyki
nazywamy
gramatykami bezkontekstowymi
lub
gramatykami klasy „2”
. Termin
„bezkontekstowy” pochodzi od tego, że produkcje takiej gramatyki pozwalają na
bezwarunkowe (bez uwzględniania kontekstu) zastąpienie nieterminala
A
łańcuchem
β
.
Języki generowane przez gramatyki tego typu noszą nazwę
języków bezkontekstowych
.
Przez
G
BK
oznaczymy klasę gramatyk kontekstowych, a przez
L
BK
klasę języków
kontekstowych.
Problem: czy x
L(G) jest rozstrzygalny dla G
G
BK
.
Ponadto:
G
BK
G
K
G
KOMB
L
RP
Klasa gramatyk bezkontekstowych jest chyba najważniejszą (z naszego punktu widzenia)
klasą gramatyk, gdyż za pomocą gramatyk tej klasy opisuje się składnię większości języków
programowania.
L
K
Klasa 3
Gramatykę
G = <N, T, P, Z>
, w której każda produkcja ma postać
A
xB
lub
A
x
gdzie
A
i
B
są nieterminalami
(A,B
N)
, zaś łańcuch
x
jest dowolnym łańcuchem
T
*
)
nazywamy
gramatyką prawostronnie liniową
.
Gramatykę
G = <N, T, P, Z>
, w której każda produkcja ma postać
A
Bx
lub
A
x
gdzie
A
i
B
są nieterminalami
(A,B
N)
, zaś łańcuch
x
jest dowolnym łańcuchem
symboli terminalnych tej gramatyki
(x
T
*
)
nazywamy
gramatyką lewostronnie liniową
.
Klasa 1
Gramatykę
G = <N, T, P, Z>
, w której produkcje mają postać
α
czym
β
nieterminalem
(A
L
BK
symboli terminalnych tej gramatyki
(x
Gramatyki prawostronnie liniowe i lewostronnie liniowe nazywamy
gramatykami liniowymi
,
gramatykami regularnymi
lub gramatykami klasy „3”
.
Języki generowane przez gramatyki tego typu noszą nazwę
języków regularnych
.
Przez
G
RG
oznaczymy klasę gramatyk regularnych, a przez
L
RG
klasę języków regularnych.
Problem: czy x
L(G) jest rozstrzygalny dla G
G
RG
.
Ponadto:
G
RG
G
BK
G
K
G
KOMB
L
RP
Klasa gramatyk regularnych jest także bardzo ważną (z naszego punktu widzenia) klasą
gramatyk, gdyż za pomocą gramatyk tej klasy opisuje się składnię większości podstawowych
elementów leksykalnych (słownikowych) języków programowania (takich jak identyfikatory,
stałe numeryczne, stałe tekstowe, komentarze, operatory, itd.
L
BK
L
K
Przykład:
Rozważymy gramatykę G = <N, T, P, Z>, w której:
N = {S, A, B, C, D, E, F, G}
T = {a, b, c}
P = {
S
AbC | aD | AE | aBc | abc
A
a
B
b
bC
bc
D
bc
aE
abFcG
F
bcG
bc
}
Z = S
Ta gramatyka jest gramatyką kombinatoryczną (klasy „0” – w lewych stronach produkcji
występują dowolne łańcuchy symboli, są dwie produkcje skracające) i równocześnie nie jest
gramatyką żadnej węższej klasy. Język przez nią generowany jest oczywiście językiem
rekurencyjnie przeliczalnym. Zbadajmy, jakie słowa są generowane przez tę gramatykę.
S
AbC
abC
ąbc
S
aD
abc
S
AE
aE
abFcG
abcG
abc
S
aBc
abc
abc
Widać, że jedynym słowem generowanym przez tę gramatykę jest
abc
. Dla języka
L = { abc }
można zbudować znacznie prostszą gramatykę G
1
= <N
1
, T, P
1
, Z>, w której:
1
= {S}
T = {a, b, c}
P
1
= { S
abc }
L
RG
S
Z = S
Gramatyka
G
1
należy do klasy „3” gramatyk regularnych. Ponieważ
L = L(G) = L(G
1
)
więc język
L
należy do klasy języków regularnych, mimo że może być wygenerowany przez
gramatykę znacznie szerszej klasy (gramatykę bez ograniczeń).
Uwaga: zawsze interesować nas będzie najwęższa klasa, do której należy badany język.
Plik z chomika:
kkkate
Inne pliki z tego folderu:
TI-teoria.pdf
(115 KB)
zajecia3.pdf
(74 KB)
2-2-gramatyki.pdf
(103 KB)
Języki formalne _ zaliczenie wykładów_ sciaga.doc
(97 KB)
algorytmy.pdf
(206 KB)
Inne foldery tego chomika:
Narzędzia Informatyki - wykłady J. Kaczmarek
Zgłoś jeśli
naruszono regulamin