3
It's true.
If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar. You already know how to do that in cubic time.
If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.
3
Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs:
$$
w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m},
$$
where all indices other than possibly $i_1,j_m$ are strictly positive.
A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are ...
3
The PDA first guesses whether $m=n$ or $n=k$. According to the guess, it either just checks that $m=n$, or just checks that $n=k$.
What your heuristic argument suggests is that this language cannot be accepted by a deterministic PDA. You can likely show this by adapting the proof here.
2
Condition 3 as in the question, "$\forall i >0, \exists z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we &...
2
Indeed, $abaaabbb \notin L_1$ because the string is not of the form $(a^nb^n)^m$ which is the repetition of a fixed string with the same number of $a$ and $b$.
The language $L_2$ is the Kleene closure of $\{a^nb^n \mid n\ge1\}$, consisting of all arbitrary concatenations of strings of the form $a^nb^n$. We can choose different strings of this form, and do ...
2
This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities;
$\begin{align*}
E &\to E + T \mid E - T \mid T \\
T &\to T * F \mid T / F \mid F \\
F &\to x \mid y \mid ( E )
\end{align*}$
You could also go ...
1
This is what we have at our hand.
Now let us see what can be get from the second production in red.
From the production in Blue we have
And the parsing can be stopped using $S\rightarrow \epsilon$
So from the above two work outs we find that the $a$'s and $b$'s are properly nested. (and can be mapped to the problem of valid parenthesization )
That being ...
1
You are quite close to the solution. We will use a few variables, each corresponding (intuitively) to some other "thing". Specifically, we will use the variables $S,E,A,B$.
$S$ is the starting variable. $E$ is a variable that will produce a valid regular expression (its called $E$ as short for "expression"). $A$ will be some valid string ...
Only top voted, non community-wiki answers of a minimum length are eligible
