Gramatyki zwykłe i bezkontekstowe

Question 1

Przygotowuję się do testu z języków komputerowych i jest jeden pomysł, że mam problemy ze zrozumieniem.

Zrozumiałem, że zwykłe gramatyki są prostsze i nie mogą zawierać niejednoznaczności, ale nie mogą wykonywać wielu zadań wymaganych w językach programowania. Zrozumiałem również, że gramatyki bezkontekstowe pozwalają na niejednoznaczność, ale pozwalają na pewne rzeczy niezbędne dla języków programowania (np. Palindromy).

To, z czym mam problem, to zrozumienie, w jaki sposób mogę wyprowadzić wszystkie powyższe informacje, wiedząc, że nieterminały gramatyki regularnej mogą mapować do terminala lub nieterminala, po którym następuje terminal, lub że bezkontekstowe mapowanie nieterminala do dowolnej kombinacji terminali i nieterminali .

Czy ktoś może mi pomóc połączyć to wszystko razem?

Question 2

Gramatyka regularna jest liniowa w prawo lub w lewo, podczas gdy gramatyka bezkontekstowa to w zasadzie dowolna kombinacja terminali i nieterminali. Stąd widać, że gramatyka regularna jest podzbiorem gramatyki bezkontekstowej.

Na przykład dla palindromu ma postać

S->ABA
A->something
B->something

Widać wyraźnie, że palindromów nie można wyrazić w gramatyce regularnej, ponieważ musi być liniowa w prawo lub w lewo i jako taka nie może mieć nieterminalnego wyrażenia po obu stronach.

Ponieważ gramatyki regularne nie są niejednoznaczne, istnieje tylko jedna reguła produkcji dla danego nieterminala, podczas gdy w przypadku gramatyki bezkontekstowej może być więcej niż jedna.

Question 3

Myślę, że chcesz pomyśleć o różnych lemmatach o pompowaniu. Język regularny może zostać rozpoznany przez automat skończony. Język bezkontekstowy wymaga stosu, a język wrażliwy na kontekst wymaga dwóch stosów (co jest równoważne stwierdzeniu, że wymaga pełnej maszyny Turinga).

Tak więc, jeśli pomyślimy o lemacie pompowania dla języków regularnych , zasadniczo mówi on, że każdy język regularny można podzielić na trzy części, x , y i z , gdzie wszystkie wystąpienia języka znajdują się w xy * z (gdzie * jest powtórzeniem Kleene, tj. 0 lub więcej kopii y .) W zasadzie masz jeden „nieterminal”, który można rozwinąć.

A co z językami bezkontekstowymi? Istnieje analogiczny lemat o pompowaniu dla języków bezkontekstowych, który dzieli ciągi w języku na pięć części, uvxyz , i gdzie wszystkie wystąpienia języka są w uv ⁱ xy ⁱ z , dla i ≥ 0. Teraz masz dwa „nieterminale "które można powielić lub pompować, o ile masz ten sam numer .

Question 4

Różnica między gramatyką regularną i bezkontekstową: (N, Σ, P, S): terminale, nieterminale, produkcje, stan początkowy Symbole terminali

● elementarne symbole języka określone przez gramatykę formalną

● abc

Symbole nieterminalne (lub zmienne składniowe)

● zastąpione grupami symboli terminali zgodnie z zasadami produkcji

● ABC

gramatyka regularna: prawa lub lewa gramatyka regularna prawa gramatyka regularna, wszystkie zasady są zgodne z formami

B → a, gdzie B jest nieterminalem w N, a a jest terminalem w Σ
B → aC, gdzie B i C są w N, a a jest w Σ
B → ε, gdzie B jest w N, a ε oznacza pusty łańcuch, czyli ciąg o długości 0

zostawił gramatykę regularną, wszystkie reguły są zgodne z formularzami

A → a, gdzie A jest nieterminalem w N, a a jest terminalem w Σ
A → Ba, gdzie A i B są w N, a a jest w Σ
A → ε, gdzie A jest w N, a ε jest łańcuchem pustym

gramatyka bezkontekstowa (CFG)

○ gramatyka formalna, w której każda reguła produkcji ma postać V → w

○ V jest pojedynczym nieterminalnym symbolem

○ w to ciąg terminali i / lub nieterminali (w może być puste)

Question 5

Gramatyka regularna: - gramatyka zawierająca produkcję w następujący sposób to RG:

V->TV or VT
V->T

gdzie V = zmienna i T = terminal

RG może być lewą gramatyką liniową lub prawą gramatyką liniową, ale nie środkową gramatyką liniową.

Jak wiemy, wszystkie RG to Linear Grammar, ale tylko Left Linear lub Right Linear Grammar są RG.

Zwykła gramatyka może być niejednoznaczna.

S->aA|aB
A->a
B->a

Niejednoznaczna gramatyka: - dla łańcucha x istnieje więcej niż jeden LMD lub Więcej niż RMD lub Więcej niż jedno drzewo analizy lub Jedno LMD i jedno RMD, ale oba produkują różne drzewo analizy.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

ta Gramatyka jest niejednoznaczna Gramatyka, ponieważ dwa drzewa parsowania.

CFG: - gramatyka nazywana CFG, jeśli jej produkcja ma postać:

   V->@   where @ belongs to (V+T)*

DCFL: - jak wiemy, wszystkie DCFL to LL (1) Gramatyka, a wszystkie LL (1) to LR (1), więc nigdy nie jest niejednoznaczne. więc DCFG nigdy nie jest niejednoznaczne.

Wiemy również, że wszystkie RL to DCFL, więc RL nigdy nie jest niejednoznaczne. Zauważ, że RG może być niejednoznaczne, ale RL nie.

CFL: CFl Może być niejednoznaczny lub nie.

Uwaga: RL nigdy nie będzie z natury niejednoznaczne.

Question 6

Wyrażenia regularne

Podstawy analizy leksykalnej
Reprezentuj języki regularne

Gramatyki bezkontekstowe

Podstawy parsowania
Reprezentuj konstrukcje językowe

wprowadź opis obrazu tutaj

Question 7

Gramatyka jest bezkontekstowa, jeśli wszystkie reguły produkcji mają postać: A (to znaczy lewa strona reguły może być tylko pojedynczą zmienną; prawa strona jest nieograniczona i może być dowolną sekwencją terminali i zmiennych). Możemy zdefiniować gramatykę jako czteroosobową krotkę, gdzie V to skończony zbiór (zmienne), _ to skończony zbiór (terminale), S to zmienna początkowa, a R to skończony zbiór reguł, z których każda jest odwzorowaniem V
gramatyka regularna jest liniowa w prawo lub w lewo, podczas gdy gramatyka bezkontekstowa jest w zasadzie dowolną kombinacją terminali i nieterminali. stąd możemy powiedzieć, że gramatyka regularna jest podzbiorem gramatyki bezkontekstowej. Po tych właściwościach możemy powiedzieć, że zestaw języków wolnych od kontekstu zawiera również zestaw języków regularnych

Question 8

Zasadniczo gramatyka regularna jest podzbiorem gramatyki bezkontekstowej, ale nie możemy powiedzieć, że każda gramatyka bezkontekstowa jest gramatyką regularną. Głównie gramatyka bezkontekstowa jest niejednoznaczna, a gramatyka regularna może być niejednoznaczna.

Question 9

gramatyka regularna nigdy nie jest niejednoznaczna, ponieważ jest albo lewostronna, albo prawostronna, więc nie możemy utworzyć dwóch drzew decyzyjnych dla gramatyki regularnej, więc jest ona zawsze jednoznaczna. ale poza gramatyką regularną wszystkie mogą być regularne lub nie

Answer 1

Przygotowuję się do testu z języków komputerowych i jest jeden pomysł, że mam problemy ze zrozumieniem.

Zrozumiałem, że zwykłe gramatyki są prostsze i nie mogą zawierać niejednoznaczności, ale nie mogą wykonywać wielu zadań wymaganych w językach programowania. Zrozumiałem również, że gramatyki bezkontekstowe pozwalają na niejednoznaczność, ale pozwalają na pewne rzeczy niezbędne dla języków programowania (np. Palindromy).

To, z czym mam problem, to zrozumienie, w jaki sposób mogę wyprowadzić wszystkie powyższe informacje, wiedząc, że nieterminały gramatyki regularnej mogą mapować do terminala lub nieterminala, po którym następuje terminal, lub że bezkontekstowe mapowanie nieterminala do dowolnej kombinacji terminali i nieterminali .

Czy ktoś może mi pomóc połączyć to wszystko razem?

Answer 2

70

Gramatyka regularna jest liniowa w prawo lub w lewo, podczas gdy gramatyka bezkontekstowa to w zasadzie dowolna kombinacja terminali i nieterminali. Stąd widać, że gramatyka regularna jest podzbiorem gramatyki bezkontekstowej.

Na przykład dla palindromu ma postać

S->ABA
A->something
B->something

Widać wyraźnie, że palindromów nie można wyrazić w gramatyce regularnej, ponieważ musi być liniowa w prawo lub w lewo i jako taka nie może mieć nieterminalnego wyrażenia po obu stronach.

Ponieważ gramatyki regularne nie są niejednoznaczne, istnieje tylko jedna reguła produkcji dla danego nieterminala, podczas gdy w przypadku gramatyki bezkontekstowej może być więcej niż jedna.

Sujoy
źródło

13

Po pierwsze: zwykłe gramatyki mogą być niejednoznaczne (na przykład z Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). Jedyną rzeczą jest to, że istnieje tylko jeden sposób, w jaki można umieścić węzły w drzewie składni (na przykład niejednoznaczność asocjatywności nie istnieje, gdy używana jest gramatyka regularna). Po drugie: nieterminal może mieć więcej niż jedną prawą stronę (A -> a, A -> aA; a wikipedia zawiera nawet epsilon jako trzecią alternatywę: en.wikipedia.org/wiki/Regular_grammar )

user764754

1

dwuznaczność pojawia się, gdy zdanie można wyprowadzić z gramatyki na więcej niż jednej ścieżce. po prostu posiadanie więcej niż jednej reguły tworzenia dla nieterminala nie sprawia, że gramatyka jest niejednoznaczna

Sujoy,

11

Ten przykład jest rzeczywiście błędny. Jeśli wyobrazimy sobie pełne reguły, A-> a | ca B->bwtedy ta gramatyka dopuszcza inne niż palindromy. Na przykład, mogę produkować: S->ABA->aBA->abA->abc. Problem polega na tym, że w pierwszej regule nie chcemy tworzyć dwóch zmiennych, ale raczej dwa terminale. Możliwość gramatyki, która dopuszcza palindromy to:S -> aSa | bSb | a | b

gdiazc

Istnieją palindromy, które można wyrazić zwykłą gramatyką: palindromy składające się z jednego znaku. Na przykład, S -> aSa | ei a(aa)*aoba opisują język regularny. To pokazuje, że CFG może opisywać zwykły język, nawet jeśli narusza lewą lub prawą liniowość. Trzeba przyznać, że to nie tak oczywisty palindrom ...

Martijn

Pomyśl o tym, ta odpowiedź jest w rzeczywistości błędna. Mówi, że gramatyka „bezkontekstowa” jest w zasadzie dowolną kombinacją terminali i nieterminali. ”Jednak tu ^ nvw ^ mxy ^ kz jest kombinacją terminali i nieterminali, ale nie jest bezkontekstowa.

Charlie Martin,

Answer 3

13

Po pierwsze: zwykłe gramatyki mogą być niejednoznaczne (na przykład z Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). Jedyną rzeczą jest to, że istnieje tylko jeden sposób, w jaki można umieścić węzły w drzewie składni (na przykład niejednoznaczność asocjatywności nie istnieje, gdy używana jest gramatyka regularna). Po drugie: nieterminal może mieć więcej niż jedną prawą stronę (A -> a, A -> aA; a wikipedia zawiera nawet epsilon jako trzecią alternatywę: en.wikipedia.org/wiki/Regular_grammar )

user764754

Answer 4

1

dwuznaczność pojawia się, gdy zdanie można wyprowadzić z gramatyki na więcej niż jednej ścieżce. po prostu posiadanie więcej niż jednej reguły tworzenia dla nieterminala nie sprawia, że gramatyka jest niejednoznaczna

Sujoy,

Answer 5

11

Ten przykład jest rzeczywiście błędny. Jeśli wyobrazimy sobie pełne reguły, A-> a | ca B->bwtedy ta gramatyka dopuszcza inne niż palindromy. Na przykład, mogę produkować: S->ABA->aBA->abA->abc. Problem polega na tym, że w pierwszej regule nie chcemy tworzyć dwóch zmiennych, ale raczej dwa terminale. Możliwość gramatyki, która dopuszcza palindromy to:S -> aSa | bSb | a | b

gdiazc

Answer 6

Istnieją palindromy, które można wyrazić zwykłą gramatyką: palindromy składające się z jednego znaku. Na przykład, S -> aSa | ei a(aa)*aoba opisują język regularny. To pokazuje, że CFG może opisywać zwykły język, nawet jeśli narusza lewą lub prawą liniowość. Trzeba przyznać, że to nie tak oczywisty palindrom ...

Martijn

Answer 7

Pomyśl o tym, ta odpowiedź jest w rzeczywistości błędna. Mówi, że gramatyka „bezkontekstowa” jest w zasadzie dowolną kombinacją terminali i nieterminali. ”Jednak tu ^ nvw ^ mxy ^ kz jest kombinacją terminali i nieterminali, ale nie jest bezkontekstowa.

Charlie Martin,

Answer 8

Myślę, że chcesz pomyśleć o różnych lemmatach o pompowaniu. Język regularny może zostać rozpoznany przez automat skończony. Język bezkontekstowy wymaga stosu, a język wrażliwy na kontekst wymaga dwóch stosów (co jest równoważne stwierdzeniu, że wymaga pełnej maszyny Turinga).

Tak więc, jeśli pomyślimy o lemacie pompowania dla języków regularnych , zasadniczo mówi on, że każdy język regularny można podzielić na trzy części, x , y i z , gdzie wszystkie wystąpienia języka znajdują się w xy * z (gdzie * jest powtórzeniem Kleene, tj. 0 lub więcej kopii y .) W zasadzie masz jeden „nieterminal”, który można rozwinąć.

A co z językami bezkontekstowymi? Istnieje analogiczny lemat o pompowaniu dla języków bezkontekstowych, który dzieli ciągi w języku na pięć części, uvxyz , i gdzie wszystkie wystąpienia języka są w uv ⁱ xy ⁱ z , dla i ≥ 0. Teraz masz dwa „nieterminale "które można powielić lub pompować, o ile masz ten sam numer .

Answer 9

10

Język wrażliwy na kontekst nie wymaga pełnej maszyny Turinga. Wystarczy automat liniowy z ograniczeniami. To jest maszyna Turinga, której taśma jest skończona, a jej rozmiar jest ograniczony jakąś funkcją liniową w ciągu wejściowym.

Dave Clarke

Answer 10

Różnica między gramatyką regularną i bezkontekstową: (N, Σ, P, S): terminale, nieterminale, produkcje, stan początkowy Symbole terminali

● elementarne symbole języka określone przez gramatykę formalną

● abc

Symbole nieterminalne (lub zmienne składniowe)

● zastąpione grupami symboli terminali zgodnie z zasadami produkcji

● ABC

gramatyka regularna: prawa lub lewa gramatyka regularna prawa gramatyka regularna, wszystkie zasady są zgodne z formami

B → a, gdzie B jest nieterminalem w N, a a jest terminalem w Σ
B → aC, gdzie B i C są w N, a a jest w Σ
B → ε, gdzie B jest w N, a ε oznacza pusty łańcuch, czyli ciąg o długości 0

zostawił gramatykę regularną, wszystkie reguły są zgodne z formularzami

A → a, gdzie A jest nieterminalem w N, a a jest terminalem w Σ
A → Ba, gdzie A i B są w N, a a jest w Σ
A → ε, gdzie A jest w N, a ε jest łańcuchem pustym

gramatyka bezkontekstowa (CFG)

○ gramatyka formalna, w której każda reguła produkcji ma postać V → w

○ V jest pojedynczym nieterminalnym symbolem

○ w to ciąg terminali i / lub nieterminali (w może być puste)

Answer 11

Gramatyka regularna: - gramatyka zawierająca produkcję w następujący sposób to RG:

V->TV or VT
V->T

gdzie V = zmienna i T = terminal

RG może być lewą gramatyką liniową lub prawą gramatyką liniową, ale nie środkową gramatyką liniową.

Jak wiemy, wszystkie RG to Linear Grammar, ale tylko Left Linear lub Right Linear Grammar są RG.

Zwykła gramatyka może być niejednoznaczna.

S->aA|aB
A->a
B->a

Niejednoznaczna gramatyka: - dla łańcucha x istnieje więcej niż jeden LMD lub Więcej niż RMD lub Więcej niż jedno drzewo analizy lub Jedno LMD i jedno RMD, ale oba produkują różne drzewo analizy.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

ta Gramatyka jest niejednoznaczna Gramatyka, ponieważ dwa drzewa parsowania.

CFG: - gramatyka nazywana CFG, jeśli jej produkcja ma postać:

   V->@   where @ belongs to (V+T)*

DCFL: - jak wiemy, wszystkie DCFL to LL (1) Gramatyka, a wszystkie LL (1) to LR (1), więc nigdy nie jest niejednoznaczne. więc DCFG nigdy nie jest niejednoznaczne.

Wiemy również, że wszystkie RL to DCFL, więc RL nigdy nie jest niejednoznaczne. Zauważ, że RG może być niejednoznaczne, ale RL nie.

CFL: CFl Może być niejednoznaczny lub nie.

Uwaga: RL nigdy nie będzie z natury niejednoznaczne.

Answer 12

4

Wyrażenia regularne

Podstawy analizy leksykalnej
Reprezentuj języki regularne

Gramatyki bezkontekstowe

Podstawy parsowania
Reprezentuj konstrukcje językowe

wprowadź opis obrazu tutaj

Ahmed Salem
źródło

Nie, to krótki opis, przeczytaj jeszcze raz i sprawdź obrazek.

Ahmed Salem

Answer 13

Nie, to krótki opis, przeczytaj jeszcze raz i sprawdź obrazek.

Ahmed Salem

Answer 14

Gramatyka jest bezkontekstowa, jeśli wszystkie reguły produkcji mają postać: A (to znaczy lewa strona reguły może być tylko pojedynczą zmienną; prawa strona jest nieograniczona i może być dowolną sekwencją terminali i zmiennych). Możemy zdefiniować gramatykę jako czteroosobową krotkę, gdzie V to skończony zbiór (zmienne), _ to skończony zbiór (terminale), S to zmienna początkowa, a R to skończony zbiór reguł, z których każda jest odwzorowaniem V
gramatyka regularna jest liniowa w prawo lub w lewo, podczas gdy gramatyka bezkontekstowa jest w zasadzie dowolną kombinacją terminali i nieterminali. stąd możemy powiedzieć, że gramatyka regularna jest podzbiorem gramatyki bezkontekstowej. Po tych właściwościach możemy powiedzieć, że zestaw języków wolnych od kontekstu zawiera również zestaw języków regularnych

Answer 15

Zasadniczo gramatyka regularna jest podzbiorem gramatyki bezkontekstowej, ale nie możemy powiedzieć, że każda gramatyka bezkontekstowa jest gramatyką regularną. Głównie gramatyka bezkontekstowa jest niejednoznaczna, a gramatyka regularna może być niejednoznaczna.

Answer 16

-4

gramatyka regularna nigdy nie jest niejednoznaczna, ponieważ jest albo lewostronna, albo prawostronna, więc nie możemy utworzyć dwóch drzew decyzyjnych dla gramatyki regularnej, więc jest ona zawsze jednoznaczna. ale poza gramatyką regularną wszystkie mogą być regularne lub nie

dinesh
źródło

4

@dinesh Zwykła gramatyka może być niejednoznaczna. Przypomnij sobie, że gramatyka jest niejednoznaczna, jeśli istnieją dwa różne drzewa składniowe i drzewo składni jest oznaczone etykietą. Stąd drzewa izomorficzne to różne drzewa. To znaczy prosta gramatyka, taka jak S -> aA | aB, B -> a, A -> a jest niejednoznaczne, ponieważ istnieją dwa drzewa składniowe dla słowa „aa”, które są izomorficzne, ale różne.

Kai Kuchenbecker

Answer 17

4

@dinesh Zwykła gramatyka może być niejednoznaczna. Przypomnij sobie, że gramatyka jest niejednoznaczna, jeśli istnieją dwa różne drzewa składniowe i drzewo składni jest oznaczone etykietą. Stąd drzewa izomorficzne to różne drzewa. To znaczy prosta gramatyka, taka jak S -> aA | aB, B -> a, A -> a jest niejednoznaczne, ponieważ istnieją dwa drzewa składniowe dla słowa „aa”, które są izomorficzne, ale różne.

Kai Kuchenbecker

Gramatyki zwykłe i bezkontekstowe

Odpowiedzi: