Gramatyka formalna

W tym dziale poznasz podstawowe pojęcia dotyczące języków formalnych oraz dowiesz się w jaki sposób definiujemy gramatykę.

Podstawowe pojęcia

Jak wiemy z poprzedniego działu,języki dzielimy na naturalne i sztuczne. Dla przypomnienia:

Język sztuczny (formalny) to ściśle określony system znaków wraz z regułami postępowania z tymi symbolami,a także regułami ich interpretowania.

Aby zdefiniować język formalny,najpierw definiujemy alfabet,wybierając jakiś niepusty zbiór skończony. Elementy takiego zbioru nazywane są symbolami. Ciągi symboli,o skończonej długości,nazywane są słowami. Zbiór słów to język formalny.

Alfabet to dowolny skończony ciąg symboli a1,a2,a3,…,an.

Alfabet oznaczamy zwykle literą V.

Przykład:

 

V={0,1,2,3,4,5,6,7,8,9}

V ={a,b,b}

V ={as,król,dama,walet}

 

Słowo (łańcuch) to dowolny skończony ciąg z powtórzeniami elementów z alfabetu V.

Zbiór wszystkich słów nad alfabetem V oznaczamy V*

Długość słowa to liczba symboli znajdująca się w łańcuchu.

Przykład:

 

|wilk| = 4

|#@$|=3

|osiemnastoliterowy|= 18

 

Symbol pusty to łańcuch nie zawierający żadnego symbolu. Oznaczany literą ε.

|ε| = 0

Operacje określone dla języków

Dla ciekawych

Złożenie języków L1 i L2 nazywamy L1L2 ={xy:x ∈ L1 ∧ y ∈ L2}

Przykładowo,jeżeli L1={a,b} i L2={c,d},to L1L2={ac,ad,bc,bd}

Potęga złożeniowa n języka L,co oznaczamy Ln,gdzie n≥0,nazywamy n-krotne złożenie języka n = L…L (n)

Możemy to także określić następująco:

L0={ε}

Ln=LLn-1

Domknięcie nieskończone języka L,co oznaczamy L*,nazywamy nowy język otrzymany w wyniku złożenia L*=df=∪i=0Li

Domknięcie dodatnie języka L,co oznaczamy L+,nazywamy nowy język otrzymany w wyniku złożenia L+=df=∪i=1Li

Zapis gramatyki

Gramatyka formalna to sposób opisu języka formalnego. Aby określić gramatykę formalną trzeba zdefiniować zbiór symboli nieterminalnych,zbiór symboli terminalnych,zbiór reguł produkcji określających w jaki sposób wyprowadzane są słowa oraz symbol początkowy.

Gramatykę formalną G zapisujemy w następujący sposób:

G = <N,V,P,S>

gdzie:

N - alfabet nieterminalny (zbiór symboli pomocnicznych)
V - alfabet terminalny (symbole,z którego tworzone są słowa języka)
P - zbiór reguł produkcji
S - symbol startowy (wyróżniony symbol nieterminalny)

Przykład:

Gramatyka generująca liczbę binarną

 

G = <N,V,P,S>

N ={<liczba binarna>,<cyfra>}

V ={0,1 }

P = <liczba binarna>::= <liczba binarna><cyfra>

<liczba binarna>::= <cyfra>

<cyfra>::= 0 | 1

S = <liczba binarna>

Pytania sprawdzające

  • Czy alfabetem może być zbiór liczb naturalnych?
  • Jaka jest długość słowa „siedem”?
  • Czy symbol startowy S służący do określenia gramatyki może być symbolem terminalnym?

Jeżeli masz wątpliwości,zapoznaj się jeszcze raz z powyższymi informacjami.