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.
źródło
Odpowiedzi:
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.
źródło