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

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?

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.

$L$

$\mathcal{A}$$L(\mathcal{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) .

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.

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 .

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

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.

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.

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.

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ą.