Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to:
Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią.
Widziałem, że automat ograniczany liniowo jest bezpośrednio poniżej decydującego w porządku tego artykułu. Jeśli tak jest, oznacza to, że każde obliczenie na LBA zatrzyma się w pewnym momencie (ponieważ każdy LBA byłby decydujący). Ale czuję, że mogą istnieć pewne obliczenia, które mogą działać na LBA w tym samym czasie, aby nigdy się nie zatrzymać. Na przykład możemy napisać obliczenia na LBA, które by to zrobiły
- przeczytaj pierwszy symbol na taśmie i przejdź w prawo;
- przeczytaj następny symbol i cofnij się w lewo.
To (bezużyteczne) obliczenie (które jest oczywiście obliczeniem LB) działałoby w nieskończoność oscylując w lewo i w prawo i nigdy się nie zatrzymywało, a zatem nie może być decydujące. Gdzie myślę źle?
Odpowiedzi:
Po pierwsze, wszystkie języki kontekstowe są rozstrzygalne, ponieważ mogą być zaakceptowane przez LBA (jak powiedziałeś), a maszyna Turinga ma większą moc niż LBA.
źródło
Proponuję rzucić okiem na tę książkę: Wprowadzenie do języków i teorii obliczeń Johna E. Martina
strona 283: Nadal istnieją pytania dotyczące języków kontekstowych, takie jak to, czy każda CSL może zostać zaakceptowana przez deterministyczny LBA.
źródło