# Tag Info

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