To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
2.2. Gramatyki, wyprowadzenia
Gramatyka
Gramatyką G nazywamy czwórkę uporządkowaną
G =
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
α, β, γ, δ, ψ, ω ∈ (N∪T)*
Słowo ψ jest wyprowadzalne ze słowa ω w gramatyce G, co zapisujemy
ω ⇒G+ ψ
jeżeli istnieją φ0, φ1, ... ,φn ∈ (N∪T)* takie, że:
φ0 = ω
φn = ψ
dla i = 1, 2, ..., n
φi-1 ⇒G φi
Sekwencję φ0, φ1, ... ,φn nazywamy wyprowadzeniem o długości n.
Definiujemy ponadto:
( ω ⇒G* ψ )
⇔ ( ω ⇒G+ ψ ) ∨ ( ω = ψ )
Relacje ⇒G+ oraz ⇒G* są odpowiednio przechodnim oraz przechodnim i zwrotnym
domknięciem relacji bezpośredniej wyprowadzalności ⇒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ę.
L(G) = { x ∈ T* | Z ⇒G* x }
Forma zdaniowa
Łańcuch x ∈ (N∪T)* nazywamy formą zdaniową gramatyki G, jeśli można go
wyprowadzić z symbolu początkowego Z.
x ∈ (N∪T)* jest formą zdaniową ⇔ Z ⇒G* x
Uwaga: terminu słowo używamy w rozumieniu łańcucha zbudowane wyłącznie z symboli
terminalnych
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 = , w której produkcje mają postać α → β , gdzie α i β są
dowolnymi łańcuchami symboli tej gramatyki, przy czym α ≠ ε 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 GKOMB oznaczymy klasę gramatyk kombinatorycznych, a przez LRP 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
... zobacz całą notatkę
Komentarze użytkowników (0)