Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.
What complexity class does this correspond to?
Related questions:
What complexity class does is this set of grammars? L-complete?
What complexity class does is this set of grammars? NL-complete?
What complexity class is this set of grammars? In between NL and P?
-
$\begingroup$ If you allow $X \to \epsilon,ドル you get unrestricted grammars. In the other direction, every context-sensitive grammar can be put in your form. $\endgroup$Yuval Filmus– Yuval Filmus2020年04月19日 15:58:18 +00:00Commented Apr 19, 2020 at 15:58
-
$\begingroup$ @Yuval Filmus: "In the other direction" Are you saying ((context-sensitve) < (this) < (Unrestricted)) or ((context-sensitve) = (this) < (Unrestricted))? $\endgroup$Jesus is Lord– Jesus is Lord2020年04月20日 16:24:06 +00:00Commented Apr 20, 2020 at 16:24
-
$\begingroup$ The first option. $\endgroup$Yuval Filmus– Yuval Filmus2020年04月20日 16:44:56 +00:00Commented Apr 20, 2020 at 16:44
-
$\begingroup$ @Yuval Filmus: Thanks! Do we know ((this) < (Unrestricted)) vs ((this) <= (Unrestricted))? We could introduce a terminal to represent the empty string input so that every string has length at least 1. $\endgroup$Jesus is Lord– Jesus is Lord2020年04月20日 16:53:07 +00:00Commented Apr 20, 2020 at 16:53
-
$\begingroup$ @Yuval Filmus: If we introduced a new terminal to represent the empty string, $e,ドル could we add one rule per non-terminal, $A$: $Ae \to A$ and generate the same strings? $\endgroup$Jesus is Lord– Jesus is Lord2020年04月20日 16:57:49 +00:00Commented Apr 20, 2020 at 16:57
1 Answer 1
Every unrestricted grammar can be converted to one with the following types of rules: $$ AB \to CD \\ A \to BC \\ A \to a \\ A \to \epsilon $$ Wikipedia calls this Kuroda normal form for unrestricted grammars.
You can convert a rule of the form $AB \to CD$ to a pair of rules $AB \to X_{ABCD}$, $X_{ABCD} \to CD$. Following the OP's suggestion, we can convert $A \to \epsilon$ to the rule $A \to E$, and add rules $BE \to B$ and $EB \to B$ for any nonterminal $B$. This allows us to obtain a grammar in your form equivalent to the original one, up to not being able to generate $\epsilon$.
-
1$\begingroup$ Maybe it would be good to point out that this implies that the associated complexity class is RE, to have a direct answer to the original question. Sorry if I'm wrong and this doesn't follow, but the restriction of not being able to generate $\epsilon$ shouldn't matter for this. $\endgroup$Bernardo Subercaseaux– Bernardo Subercaseaux2020年05月20日 19:38:32 +00:00Commented May 20, 2020 at 19:38
-
$\begingroup$ Right, I left this final step to the reader. $\endgroup$Yuval Filmus– Yuval Filmus2020年05月20日 19:51:52 +00:00Commented May 20, 2020 at 19:51