Czy można rozstrzygać o równoważności jednoznacznych języków bezkontekstowych?

19

Dobrze wiadomo, że problem równoważności jest nierozstrzygalny dla ogólnych języków bezkontekstowych. Jednak wszystkie dowody tego faktu, o których jestem świadomy, wydają się obejmować pewne niejednoznaczne gramatyki bezkontekstowe. Z tego powodu chciałbym zapytać, czy wiadomo, czy problem pozostaje nierozstrzygalny, ograniczając się do jednoznacznych języków bezkontekstowych. To znaczy, biorąc pod uwagę dwie bezkontekstowe gramatyki, które z góry są jednoznaczne, czy można rozstrzygnąć, czy są one równoważne, czy nie?

Uważam ten problem za nieco intrygujący, ponieważ wiadomo, że równoważność jest rozstrzygalna w przypadku deterministycznych języków bezkontekstowych, chociaż wynik ten nie jest trywialny ... Z drugiej strony, może istnieć prosty powód nierozstrzygalności, że byłem niewidzenie.

Jára Cimrman
źródło
3
Włączenie jest nierozstrzygalne: pdfs.semanticscholar.org/afdb/…
Peter Leupold
4
@PeterLeupold Tak, ale dołączenie jest nierozstrzygalne również w przypadku deterministycznych języków bezkontekstowych, więc jest to dość proste (artykuł, do którego linkujesz, po prostu daje dowód bez użycia tego faktu). Jednak równoważność wydaje się o wiele bardziej interesująca, ponieważ jest to rozstrzygalne w przypadku deterministycznych języków bezkontekstowych i nierozstrzygalne w przypadku ogólnych języków bezkontekstowych ...
Jára Cimrman
3
Niemniej jednak zaczynam podejrzewać, że problem ten może być otwarty: dowód rozstrzygalności jest mało znany, ponieważ dowód na deterministyczne świetlówki kompaktowe jest dość skomplikowany; z drugiej strony nierozstrzygalność oznaczałaby nierozstrzygalność równoważności szeregu algebraicznego w zmiennych nieprzemiennych, co, jeśli dobrze zrozumiałem wszystko, powinno być otwartym problemem. N.
Jára Cimrman,

Odpowiedzi:

9

Jest to obecnie otwarty problem. Jak słusznie wskazano, jeśli jest to rozstrzygalne, to oczekuje się, że dowód będzie trudny, ponieważ uogólnia znany problem równoważności DPDA. Z drugiej strony, klasyczne argumenty za nierozstrzygalnością problemu uniwersalności CFL wykorzystują z natury niejednoznaczne języki, a zatem potrzebne są nowe pomysły, aby pokazać nierozstrzygalność.

Zaznaczę , że problem uniwersalności dla UCFL jest rozstrzygalny (w PSPACE), przy użyciu funkcji generujących [1].

BIBLIOGRAFIA

[1] N. Chomsky i poseł Schützenberger, Algebraiczna teoria języków bezkontekstowych, programowanie komputerowe i systemy formalne, 1963.

Lorenzo
źródło
2
Myślę, że masz na myśli z natury dwuznaczne języki.
Emil Jeřábek wspiera Monikę
w rzeczy samej, dziękuję @ EmilJeřábek za zauważenie tego
Lorenzo,