# Tag Info

## Hot answers tagged automata

3

From the supplied solution, it's clear that the question was written incorrectly. The fifth, sixth and seventh productions should produce $X$, $Y$ and $Z$, respectively, instead of $A$, $B$ and $C$. You might want to report this typo to whomever set the problem. Once you make that change, the fact that it is equivalent to a right-linear grammar can be shown ...

2

$L(G)$ is regular and hence not inherently ambiguous. In particular $L(G)$ is the language described by the regular expression $a(xa)^*$.

2

Indeed $L = \Sigma^\ast$. Here is a proof. Clearly, $L \subseteq \Sigma^\ast$, so it suffices to show $\Sigma^\ast \subseteq L$. Let $w \in \Sigma^\ast$. We start with an arbitrary decomposition $w = uv$. If $|u|_a = |v|_b$ we are done. Otherwise, wlog let $|u|_a < |v|_b$. Then by moving the cutpoint one step to the right, i.e. considering the ...

1

If you look at the formal definition of grammars, there is nothing requiring a nonterminal symbol to apppear in the left side of a production rule. So $G$ is a perfectly valid grammar. If we drop all useless production we are left with $S \to \lambda$. Therefore $L(G) = \{ \lambda\}$, which is a finite language and hence it is also regular. If you really ...

1

You should take a look at Berry-Sethi's algorithm for the general method (+ powerset construction for a DFA).

1

There is no discrepancy in the two methods. The first method shows that $L := \overline{\overline{L_1} \cup \overline{L_2}}$ is context-sensitive. The second method shows the stronger result that $L$ is context-free. Both of these are consistent. Compare the following: $$1 + 1 \leq 1 + 2 = 3 \Longrightarrow 1 \leq 3 \\ 1 + 1 \leq 2$$ The first inequality ...

1

actually you also had a mistake in the definition of the problem and I've considered its |Wa|=|Wb| or |Wa|=|Wc|. Any way using non-deterministic I've tried to separate two conditions:

Only top voted, non community-wiki answers of a minimum length are eligible