Co to jest gramatyka bezkontekstowa?

104

Czy ktoś może mi wyjaśnić, czym jest gramatyka bezkontekstowa? Po przejrzeniu wpisu w Wikipedii, a następnie wpisu w Wikipedii dotyczącego gramatyki formalnej, jestem całkowicie zdezorientowany. Czy ktoś byłby tak miły i wyjaśniłby, czym są te rzeczy?

Zastanawiam się nad tym, ponieważ chcę zbadać analizę składniową, a także na marginesie, ograniczenie silnika regex.

Nie jestem pewien, czy te terminy są bezpośrednio związane z programowaniem, czy też są związane bardziej z językoznawstwem w ogóle. Jeśli tak jest, przepraszam, może można by to przenieść, jeśli tak?

Łokieć
źródło
2
To jest bardziej związane zAutomata Theorem
Rahul
2
Jeśli interesują Cię języki formalne i teoria automatów do analizowania, proponuję książkę taką jak Języki i maszyny Sudkampa lub Aho, Sethi & Ullman's Compilers . Każda książka zawiera formalny opis gramatyki bezkontekstowej, która jest rodzajem gramatyki formalnej, a następnie stwierdza i udowadnia podstawowe twierdzenia dotyczące gramatyk bezkontekstowych wymaganych do ich zrozumienia (takich jak lemat o pompowaniu dla języków bezkontekstowych i konwersji oraz twierdzenia o postaci normalnej). Nie ma żadnego matematycznego warunku wstępnego uczenia się formalnej teorii języka poza pobieżnym zrozumieniem teorii mnogości.
danportin
1
Czy nie należy przenosić takich pytań do Informatyki Teoretycznej?
Pale Blue Dot,

Odpowiedzi:

110

Gramatyka bezkontekstowa to gramatyka spełniająca określone właściwości. W informatyce gramatyki opisują języki; w szczególności opisują języki formalne.

Język formalny to po prostu zbiór (termin matematyczny na zbiór obiektów) ciągów (sekwencji symboli ... bardzo podobny do użycia słowa „łańcuch” w programowaniu). Prostym przykładem języka formalnego jest zbiór wszystkich ciągów binarnych o długości trzy, {000, 001, 010, 011, 100, 101, 110, 111}.

Gramatyki działają poprzez definiowanie przekształceń, które możesz wykonać, aby skonstruować ciąg w języku opisanym przez gramatykę. Gramatyka powie, jak przekształcić symbol początkowy (zwykle S) w jakiś ciąg symboli. Gramatyka dla podanego wcześniej języka to:

S -> BBB
B -> 0
B -> 1

Sposobem na zinterpretowanie tego jest stwierdzenie, że Smożna go zastąpić BBBi Bzastąpić przez 0, a także Bprzez 1. Tak więc skonstruować łańcuch 010, możemy zrobić S -> BBB -> 0BB -> 01B -> 010.

Gramatyka bezkontekstowa to po prostu gramatyka, w której element, który zastępujesz (na lewo od strzałki), jest pojedynczym symbolem „nieterminalowym”. Symbol nieterminalny to dowolny symbol używany w gramatyce, który nie może pojawić się w końcowych napisach. W gramatyce powyżej „S” i „B” to symbole nieterminalne, a „0” i „1” to symbole „końcowe”. Gramatyki jak

S -> AB
AB -> 1
A -> AA
B -> 0

Nie są regularne, ponieważ zawierają reguły takie jak „AB -> 1”.

aegrisomnia
źródło
12
Mówiąc „nie zwykły”, masz na myśli „nie bezkontekstowy”? (ponieważ język reprezentowany przez CFG jest super zestawem języków, które można przedstawić za pomocą wyrażeń regularnych)
Anti Earth
3
Czy „S można zastąpić B” czytać „S można zastąpić BBB”?
Cosmo Harrigan
4
Dobry Boże, to jedna z najlepiej wyjaśnionych odpowiedzi, jakie widziałem w SO.
Rafael Dias da Silva
1
@AntiEarth drugi przykład nie jest gramatyką regularną, ponieważ ma reguły, które generują dwa symbole nieterminalne z jednego symbolu nieterminalnego, co jest niedozwolone w gramatykach regularnych (również, jak wskazał OP, ma reguły z wieloma symbolami nieterminalnymi lewo). en.wikipedia.org/wiki/Regular_grammar
awwsmm
21

Teoria języka jest powiązana z teorią obliczeń. Jaka jest bardziej filozoficzna strona informatyki, o decydowaniu, które programy są możliwe lub które kiedykolwiek będzie można napisać, i jakiego rodzaju problemów nie da się napisać algorytmu do rozwiązania.

Wyrażenie regularne to sposób opisu języka regularnego. Język regularny to język, o którym decyduje deterministyczny automat skończony.

Powinieneś przeczytać artykuł o maszynach skończonych: http://en.wikipedia.org/wiki/Finite_state_machine

Oraz języki regularne: http://en.wikipedia.org/wiki/Regular_language

Wszystkie zwykłe języki są językami bezkontekstowymi, ale istnieją języki bezkontekstowe, które nie są normalne. Język wolny od kontekstu to zbiór wszystkich ciągów akceptowanych przez gramofon bezkontekstowy lub automat przesuwający, który jest maszyną skończoną z pojedynczym stosem: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Istnieją bardziej skomplikowane języki, które wymagają maszyny Turinga (dowolnego możliwego programu, który możesz napisać na swoim komputerze), aby zdecydować, czy łańcuch jest w tym języku, czy nie.

Teoria języka jest również bardzo powiązana z problemem P vs. NP i kilkoma innymi interesującymi rzeczami.

Mój podręcznik Wprowadzenie do informatyki na trzecim roku był całkiem dobry w wyjaśnianiu tego zagadnienia: Wprowadzenie do teorii obliczeń. Michael Sipser. Ale kupienie nowego kosztowało mnie około 160 dolarów i nie jest zbyt duże. Może znajdziesz używaną kopię, kopię w bibliotece lub coś, co może ci pomóc.

EDYTOWAĆ:

Ograniczenia wyrażeń regularnych i wyższych klas językowych były badane mnóstwo w ciągu ostatnich 50 lat. Może zainteresuje Cię lemat o pompowaniu dla języków regularnych. Jest to sposób na udowodnienie, że określony język nie jest regularny:

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Jeśli język nie jest zwykły, może być bezkontekstowy, co oznacza, że ​​może być opisany przez gramofon bezkontekstowy lub może być nawet w wyższej klasie językowej, możesz udowodnić, że nie jest wolny od kontekstu, lemat o pompowaniu dla programu Context Free języki, które są podobne do języka dla wyrażeń regularnych.

Język może być nawet nierozstrzygalny, co oznacza, że ​​nawet maszyna Turinga (może programować twój komputer) nie może być zaprogramowana do decydowania, czy łańcuch powinien być akceptowany tak jak w języku, czy odrzucany.

Myślę, że najbardziej interesują cię maszyny skończone (zarówno deterministyczne, jak i deterministyczne), aby zobaczyć, jakie języki może zdecydować wyrażenie regularne, oraz lemat o pompowaniu, aby udowodnić, które języki nie są regularne.

Zasadniczo język nie jest normalny, jeśli potrzebuje jakiejś pamięci lub umiejętności liczenia. Język dopasowania nawiasów nie jest regularny, na przykład, ponieważ maszyna musi pamiętać, czy otworzyła nawias, aby wiedzieć, czy musi go zamknąć.

Językiem wszystkich ciągów znaków zawierających litery a i b, które zawierają co najmniej trzy b, jest język zwykły: a ba ba ba

Język wszystkich łańcuchów wykorzystujących litery a i b, które zawierają więcej b niż a, nie jest regularny.

Nie powinieneś też, aby wszystkie skończone języki były regularne, na przykład:

Język wszystkich łańcuchów krótszych niż 50 znaków, w których występują litery a i b, które zawierają więcej b niż a, jest regularny, ponieważ jest skończony, wiemy, że można go opisać jako (b | abb | bab | bba | aabbb | ababb |. ..) ect, aż zostaną wymienione wszystkie możliwe kombinacje.

Paweł
źródło
1
Wyrażenia regularne nie są programami decyzyjnymi, które dopasowują łańcuchy do wzorców. Są to wyrażenia oznaczające zbiory regularne, dla których problem przynależności jest rozstrzygalny.
danportin
1
Jeśli zestaw jest regularny, jest to oczywiście rozstrzygalne. Nie wiem, jak inaczej to wyrazić. Są to efektywnie programy decyzyjne, które nie mają pamięci.
Paul,
Opisujesz deterministyczne automaty skończone, które zapewniają procedurę decyzyjną dla języków regularnych („programy decyzyjne, które nie mają pamięci”). Wyrażenia regularne są terminy , które oznaczające regularnych języków, nie programy są procedury. To była moja jedyna skarga.
danportin
1
Zmieniłem to na „Wyrażenie regularne to sposób opisu języka regularnego. Język regularny to język, o którym decyduje deterministyczny automat skończony”. Czy to brzmi lepiej?
Paul,