5
Let me start with a grammar for the language of words of the form $x\#x^R$:
$$
S \to aSa \mid bSb \mid \#
$$
This is our starting point. Now there are two interpretations of the term subsequence. Under the first interpretation, a subsequence is obtained by removing any number of symbols. This just means that we can omit the second side of each production of ...
5
A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA.
What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick comment that the LBA equivalence holds also in this case ... but ...
It's easy to see/prove that a 2-stack PDA with a linear bound only on one stack can simulate a ...
2
"Plugging in random terminals in $x$" is the right approach.
To implement that, we need to understand clearly how we have achieved "the concatenation of two mutually reversed strings" first. It is done by growing a string from both ends with the same symbol repeatedly, a characteristic technique for context-free grammar, as illustrated below.
$$\begin{...
2
Here's how I'd approach this:
Make a grammar that can produce palindromes
Make a grammar that can produce "any sequence of as and bs followed by #"
Make a grammar that can produce "any sequence of as and bs"
Then combine the three. $L_1$ is:
Any sequence of as and bs
The first half of a palindrome
Any sequence of as and bs followed by #
The second half of ...
2
Your language is not context-free. You can see this by applying the inverse of the homomorphism which sends $a$ to $a$, $b$ to $bb$ and $c$ to $cc$; this results in the language $\{a^ib^ic^i : i > 1\}$, which differs from a well-known non-context-free language by just a finite number of words.
2
Let $L$ be a context-free but not regular language over $\{0,1\}$ such that its complement language $\overline L$ is also context-free. Then $\overline L$ is not regular and $L\cup\overline L=\Sigma^*$ is regular.
In particular, let $L=\{a^nb^n\mid n\in\Bbb N\}$.
The previous example requires you to verify that both $L$ and $\overline L$ are context-free. ...
Only top voted, non community-wiki answers of a minimum length are eligible
