Gramatyka bezkontekstowa


Gramatyka bezkontekstowa w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Gramatyka bezkontekstowagramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:

A Γ , {\displaystyle A\to \Gamma ,}

gdzie:

A {\displaystyle A} – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje; Γ {\displaystyle \Gamma } – dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.

Formalna definicja | edytuj kod

Gramatyką bezkontekstową nazywa się czwórkę uporządkowaną ( T , N , P , S ) , {\displaystyle (T,N,P,S),} gdzie:

  • T {\displaystyle T} jest skończonym zbiorem symboli terminalnych,
  • N {\displaystyle N} jest skończonym zbiorem symboli nieterminalnych,
  • P {\displaystyle P} jest skończonym zbiorem reguł typu L R , {\displaystyle L\to R,} gdzie L N {\displaystyle L\in N} oraz R ( T N ) , {\displaystyle R\in (T\cup N)^{*},}
  • S N {\displaystyle S\in N} jest wyróżnionym elementem początkowym.

Przykłady | edytuj kod

Przykład 1
Gramatyka ( { a , b } , { S } , { S a S b | ϵ } , S ) {\displaystyle (\{a,b\},\{S\},\{S\to aSb|\epsilon \},S)} generuje język { a n b n : n N } . {\displaystyle \{a^{n}b^{n}:n\in \mathbb {N} \}.} Ten język nie jest regularny.
Przykład 2
Język { w : w { a , b } w = w R } , {\displaystyle \{w:w\in \{a,b\}^{*}\wedge w=w^{R}\},} który jest językiem wszystkich palindromów nad alfabetem { a , b } , {\displaystyle \{a,b\},} może być wygenerowany przez następującą gramatykę: ( { a , b } , { S } , { S a S a | b S b | a | b | ϵ } , S ) . {\displaystyle (\{a,b\},\{S\},\{S\to aSa|bSb|a|b|\epsilon \},S).}

Postaci normalne | edytuj kod

Każdy język bezkontekstowy nie zawierający słowa pustego może być wyrażony za pomocą gramatyki w postaci normalnej Greibach oraz postaci normalnej Chomskiego.

Na podstawie artykułu: "Gramatyka bezkontekstowa" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy