Klasy Gramatyk 1

KLASY GRAMATYK

Giamatyki klasy " O ”

a-> p

o: £ V*. p £ V+ =* w następniku nie może być słowo puste np. AabC -> Aad

Giamatyki kontekstowe (klasy ‘T'ł

o-> p

o, p € V* |o| £ |p| =4- poprzednik nie może być dłuższy od następnika np. aB -» abB

Giamatyki bezkontekstowe (klasy "2"i A-> B

A € N, B; £ V* =*• w poprzedniku tylko jeden symbol nieterminalny, w następniku dowolny kontekst np. B —> aBCa

Giamatyki lemilame (klasy "3"i

gramatyki prawostronne liniowe A-» aB B —> b

gramatyki lewostronnie liniowe A—> Ba B —» b

A, BeN; a.bGl

Przykłady

Gramatyka be z kontekstowa

Czy (x + y) * z G L(Gi)

G-i = ({W. S. C}. {x, y, z, (,). +, *}, P, W)

P; W —* W + S | s

s-> s*c i c

C -> x | y | z | (W)

W—*S—»S*C—»C*C—»(W) * C —»(W + S) * C —»(S + S) * C —* (C + S) * C —»(x + S) * C —* (x + C) * C —»(x + y) * C -*(x + y) * z G L(Gi)