W tym rozdziale poznasz cztery klasy języków formalnych wprowadzone przez Noama Chomsky’ego.
W jaki sposób stwierdzić,czy jakieś słowo należy do języka opisywanego przez daną gramatykę? Niestety nie istnieje ogólna metoda,która pozwoliłaby to zbadać dla każdej gramatyki. Dlatego w praktyce używa się wybranych klas gramatyk,dla których istnieje możliwość przeprowadzenia takiej weryfikacji. Najbardziej rozpowszechniona jest klasyfikacja gramatyk i języków wprowadzona przez Noama Chomsky’ego,która dzieli gramatyki na cztery klasy:
- Gramatyki rekurencyjnie przeliczalne –rozpoznawane jest przez maszyny Turinga
- Gramatyki kontekstowe –rozpoznawalne przez automaty liniowo ograniczone
- Gramatyki bezkontekstowe –rozpoznawalne przez automaty ze stosem
- Gramatyki regularne –rozpoznawalne przez automaty skończone
Dla ciekawych
Noam Chomsk’y to jeden z najbardziej znanych i najczęściej cytowanych profesorów lingwistyki. Wraz z Morrisem Halle opracował pojęcie gramatyki transformacyjno-generatywnej,która ma wyjaśniać kompetencje osoby mówiącej (słuchającej) w zakresie tworzenia i rozumienia wypowiedzeń danego języka. Chomsky znany jest również ze swoich radykalnych poglądów politycznych.
0 –gramatyki rekurencyjnie przeliczalne
Język rekurencyjnie przeliczalny to język,dla którego istnieje gramatyka typu 0,której produkcje są postaci α → β,gdzie α i β są dowolnymi słowami.
Dla ciekawych
Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:
- Rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem.
- Język formalny,dla którego istnieje maszyna Turinga lub inna funkcja obliczalna,która jest w stanie ponumerować wszystkie słowa języka.
- Język formalny L,dla którego problem czy słowo x ∈ L
Gramatyki klasy 0 są zbyt ogólne do opisu składni języków programowania i języków naturalnych.
1 –Gramatyki kontekstowe
Język kontekstowy to język,który można wygenerować za pomocą gramatyki kontekstowej,której produkcje są postaci α A β → α γ β,gdzie α i β są dowolnymi słowami,A symbolem nieterminalnym,γ –niepustym słowem.
Przykład:
- AB → CDB
- AB → CdEB
- ABcd → abCDBcd
- B → b
2 –Gramatyki bezkontekstowe
Język bezkontekstowy to język,który można wygenerować za pomocą gramatyki bezkontekstowej,która po lewej stronie reguł produkcji ma pojedynczy symbol nieterminalny,po prawej zaś dowolne słowa. Postać:A → γ
Przykład:
- A → aBc
Większość języków programowania należy do klasy 2.
3 –gramatyki regularne
Język regularny to język,który można wygenerować za pomocą gramatyki liniowej – takiej,która po lewej stronie reguł ma pojedynczy symbol nieterminalny,po prawej zaś słowa zawierające co najwyżej jeden symbol nieterminalny.
Przykład:
- A → ε
- A → a
- A → abc
- A → B
- A → abcB
Gramatyki regularne odgrywają bardzo ważną rolę w teorii języków i teorii automatów. Napis generowany przez gramatykę regularną jest akceptowany przez automat skończony,i na odwrót.
Dla ciekawych
Jeżeli L1 oraz L2 są regularne,to regularnymi są także następujące języki:
- L1 ∪ L2
- L1 ∩ L2
- L1 * L2 ={xy:x ∈ L1 ∧ y ∈ L2}
- L* ={ε} ∪ L ∪ L2 ∪ …
Pytania sprawdzające
- Jak wygląda klasyfikacja gramatyk wprowadzona przez Chomsky’ego?
- Która klasa gramatyk odpowiada maszynom Turinga?
Jeżeli masz wątpliwości,zapoznaj się jeszcze raz z powyższymi informacjami.