Jakie znaczenie mają języki kontekstowe (typ 1)?

34

Widząc, że w hierarchii Chomsky'ego języki Type 3 mogą być rozpoznawane przez maszynę stanową bez pamięci zewnętrznej (tj. Skończonego automatu), Type 2 przez maszynę stanową z pojedynczym stosem (tj. Automat push-down) i typ 0 przez automat stanowy z dwoma stosami (lub równoważnie taśmą, jak w przypadku maszyn Turinga), jak języki Type 1 pasują do tego obrazu? Jakie korzyści przynosi ustalenie, że językiem jest nie tylko typ 0, ale i typ 1?

maska ​​bitowa
źródło
2
Ponieważ pytasz tutaj, a nie w cstheory.SE (jak sugeruje @Sunil), proponuję również dodać krótki opis / definicję typu 1, co może nie być znanym terminem dla wszystkich.
Janoma,
5
@Sunil Nie, nie będzie. To nie jest pytanie na poziomie badawczym (a nawet gdyby tak było, nadal byłoby na ten temat, ponieważ nie wykluczamy pytań na poziomie badawczym - przynajmniej tak pamiętam, że było to wynikiem dyskusji na tym obszarze51).
sepp2k
3
@Janoma: Dlaczego warto pomagać w umieszczaniu informacji, które można łatwo wyszukać (czy nie byłoby to liczone jako hałas)?
maska ​​bitowa
4
@Janoma Myślę, że ogólną wytyczną powinno być wyjaśnienie pojęć, których ktoś, kto byłby w stanie odpowiedzieć na pytanie, mógłby nie wiedzieć (gdyby wytyczną było wyjaśnienie wszystkiego, czego nie znają niektórzy użytkownicy witryny, wyjaśnilibyśmy wszystko przez cały czas i to z pewnością nie jest standardem w innych witrynach SE). I nie sądzę, aby ktoś, kto nie zna hierarchii Chomsky'ego, byłby w stanie odpowiedzieć na pytanie. Oczywiście wyjaśnienie nie jest tak bolesne (o ile nie powoduje, że pytanie staje się nudne) - po prostu nie uważam, że jest to konieczne w tym przypadku.
sepp2k,
4
Każdy kierunek informatyki zna (lub powinien znać) hierarchię Chomsky'ego. Wszyscy inni mogą to sprawdzić w latach 20. Wystarczy link do Wikipedii .
Raphael

Odpowiedzi:

19

Języki kontekstowe to dokładnie języki, które może rozpoznać maszyna Turinga za pomocą przestrzeni liniowej i niedeterminizmu. Możesz symulować taką maszynę Turinga przy użyciu czasu wykładniczego, abyś mógł rozpoznać każdy taki język w czasie wykładniczym. Zauważ, że problem z rozpoznawaniem niektórych języków kontekstowych to -complete, co oznacza, że ​​jesteśmy prawie pewni, że nie da się poradzić lepiej niż czas wykładniczy.PSPACE

Porównując to do języków typu 0, oznacza to, że możesz przynajmniej powiedzieć coś o tym, ile czasu zajmuje rozpoznanie języka. Język typu 0 może nawet nie być rozstrzygalny: język wszystkich maszyn Turinga, który się zatrzymał, jest językiem typu 0, ale ponieważ rozpoznanie tego języka jest właśnie problemem zatrzymania, nie jest rozstrzygalne.

Gramatyki kontekstowe nie są zbyt przydatne w praktyce. Kontekstowych darmowych gramatyki są intuicyjne do pracy, ale jako przykłady Wikipedia pokazują , kontekstowych wrażliwe gramatyki bardzo szybko stają się raczej niechlujny. Programy wykorzystujące przestrzeń wielomianową są znacznie łatwiejsze do zaprojektowania (a kompletność gwarantuje istnienie jakiegoś równoważnego CSG, który jest tylko wielomianowo większy niż wykorzystanie przestrzeni przez algorytm).PSPACE

Powodem ich istnienia jest to, że tworzą one bardzo naturalne rozszerzenie gramatyki bezkontekstowej (pozwalasz kontekstowi na określenie, które produkcje są ważne). Prawdopodobnie zainspiruje to Chomsky'ego do zdefiniowania ich i nazwania ich językami typu 1. Pamiętaj, że ta definicja została stworzona, zanim komputery stały się tak szybkie, jak obecnie: bardziej interesuje się teoretykami języka formalnego niż programistami.

Nieograniczone gramatyki stają się jeszcze dziwniejsze: nie ma już pojęcia „rozszerzania” nieterminala i zastępowania go produkcją, być może w zależności od kontekstu. Możesz również dowolnie modyfikować kontekst. To sprawia, że ​​praca z nieograniczonymi gramatykami jest jeszcze mniej intuicyjna: programy są równoważne i dużo bardziej intuicyjne.

Alex ten Brink
źródło
Ale języki kontekstowe przydatne! Zobacz na przykład tę dyskusję .
Raphael
Czułość kontekstu jest przydatna, ale gramatyki kontekstowe jako sposób opisu języków nie są zbyt przydatne IMO. O wiele lepiej jest użyć innych środków do opisania funkcji kontekstowych.
Alex ten Brink
Ale w większości odpowiedzi mówisz o językach. Jeśli chodzi o gramatykę, ymmw. Istnieją modele gramatyczne między CFG i CSG, które mają naturalne zastosowania do modelowania, np. Sprzężone / wiele CFG.
Raphael
1
Masz rację, byłem niechlujny z rozróżnieniem języków i gramatyki, które widzę. Zaktualizowałem swoją odpowiedź.
Alex ten Brink
10

L

AL(A)

Krótko mówiąc, w przypadku mniejszych klas potrzebujesz mniej mocy obliczeniowej, aby rozwiązać problem decydowania o tym, czy słowo należy do języka.

Według Wikipedii Chomsky zdefiniował gramatyki kontekstowe (tj. Typ 1), aby opisać składnię języków naturalnych. Jest to nieco inne niż w przypadku innych klas języków, które zostały wprowadzone w celu opisania rodzin ciągów używanych w matematyce (np. Składnia wzorów arytmetycznych) zamiast języków naturalnych (np. Składnia zdania poprawnego gramatycznie w języku angielskim) .

Janoma
źródło
2
„Krótko mówiąc, w przypadku mniejszych klas potrzebujesz mniej mocy obliczeniowej, aby rozwiązać problem decydowania o tym, czy słowo należy do języka”. dokładnie, ale jak to się ma do typu 1 i typu 0? To jest dokładnie pytanie!
maska ​​bitowa
ccn i odpowiednio analizuje. Nie jest to możliwe w przypadku ogólnej bazy TM ani ogólnego języka typu 0.
Janoma,
8

W językach bezkontekstowych, w dowolnym momencie analizy wejściowej, automat znajduje się w stanie określonym przez stos. Każda produkcja zachowuje się tak samo pod względem zużycia danych wejściowych, niezależnie od tego, gdzie jest używana.

Prowadzi to do interesującej właściwości, że każda produkcja generuje podjęzyk języka generowanego przez te, które są głębiej w stosie, a zatem dla każdej pary A i B produkcji generowanych i zużywanych przy dowolnym określonym wkładzie mamy trzy możliwe przypadki:

  • a: Dane wejściowe zużywane przez A są całkowicie zawarte w danych wejściowych zużywanych przez B; lub
  • b: Dane wejściowe zużyte przez A całkowicie zawierają dane wejściowe zużyte przez B; lub
  • c: Dane wejściowe pobierane przez A są całkowicie niezależne od danych wejściowych pobieranych przez B.

Oznacza to, że nigdy się nie dzieje:

  • d: Dane wejściowe zużywane przez A częściowo pokrywają się z danymi wejściowymi zużywanymi przez B.

W przeciwieństwie do tego, w językach kontekstowych zachowanie każdej produkcji zależy od tego, gdzie jest używana, więc dane wejściowe zużyte w produkcji nie są podjęzykiem tych, które znajdują się głębiej na stosie (w rzeczywistości przetwarzanie ich za pomocą stos nie działa). I mamy taką możliwość, że d może się zdarzyć.

W prawdziwym świecie przypadek, w którym język kontekstowy miałby sens, to coś w rodzaju oznaczenia <b> pogrubionego tekstu </b>, <i> tekstu pochylonego </i> i <u> tekstu podkreślonego </u> za pomocą te znaczniki HTML i pozwól im się nakładać, np. „To jest <u> tekst z <i> mieszanymi </u> nakładającymi się znacznikami </i>.” Zauważ, że aby to przeanalizować i sprawdzić, czy wszystkie znaczniki początkowe pasują do znaczników końcowych, PDA nie zrobi tego, ponieważ nie jest kontekstowe, ale LBA zrobi to łatwo.

Victor Stafusa
źródło
7

Właściwości zamknięcia

Ze wszystkich klas językowych z hierarchii Chomsky'ego tylko zwykłe i kontekstowe języki są zamknięte pod uzupełnieniem . Dlatego jest to rodzaj unikalnej cechy języków kontekstowych.

W przeciwieństwie do języków bezkontekstowych, CS są również zamknięte pod skrzyżowaniem i losowym produktem .

Sebastian
źródło
6

Dowolny język typu 1 może zostać rozpoznany przez maszynę Turinga, która wykorzystuje jedynie przestrzeń liniową (tak zwane liniowe automaty ograniczone).

Suresh
źródło
2
Tak, to jest definicja. Ale w jaki sposób to ograniczenie pomaga mi?
maska ​​bitowa
3
pomaga mi to, ponieważ ogranicza moc algorytmów rozpoznających CSG do E zamiast EXP. Nie wiem, jak ci to pomaga :)
Suresh,
5

Języki typu 1 mogą być wybierane za pomocą automatów ograniczonych liniowo , które są niedeterministycznymi maszynami Turinga, które mogą wykorzystywać tylko część taśmy, której rozmiar jest liniowy do rozmiaru wejściowego.

sepp2k
źródło
4

Hierarchia Chomsky'ego klasyfikuje gramatykę bardziej niż języki. Jednak nie został zaprojektowany w taki sposób, aby miał coś wspólnego z liczbą taśm, które powinien rozpoznać automat, jak sugerowałeś dla Typu 2 i 3, nawet jeśli istnieje rodzaj maszyny Turinga, która robi to dla gramatyki Typu 1.

Należy również zauważyć, że języki gramatyki typu 0 nie są wszystkie rozpoznawane przez maszynę Turinga, ale mogą one być policzone tylko przez taką maszynę: typ 0 oznacza rekurencyjnie wyliczalną, a maszyny Turing rozpoznają tylko języki rekurencyjne.

jmad
źródło
4

Współczesny język programowania cały czas korzysta z funkcji kontekstowych; należą do podzbioru, który można skutecznie ustalić.

Przykładami są analiza nazw i typów oraz wnioskowanie o typach.

Raphael
źródło
3

Wiele innych wspomniało, że języki typu 1 to te, które można rozpoznać po automatach z ograniczeniami liniowymi. Problem zatrzymania jest rozstrzygalny w przypadku automatów z ograniczeniami liniowymi, co z kolei oznacza, że ​​wiele innych właściwości, które są nierozstrzygalne obliczeniowo dla języków rozpoznawanych przez tokarki, jest rozstrzygalnych dla języków typu 1.

Wprawdzie dowód, że problem zatrzymania jest rozstrzygalny w przypadku automatów z ograniczeniami liniowymi, opiera się na fakcie, że przy skończonej ilości taśmy mogą one wejść tylko w skończoną liczbę stanów, więc jeśli nie zatrzymają się w tak wielu krokach, wiesz, że są zapętla się i nigdy się nie zatrzyma. Ten dowód technicznie dotyczy wszystkich rzeczywistych komputerów (które mają również skończoną pamięć), ale nie ma praktycznej korzyści w rozwiązaniu problemu zatrzymania programów, które na nich działają.

Ben
źródło