patternMinor
If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?
Viewed 0 times
whatfreeaboutthencontextnot
Problem
I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack.
But, a link of Show that { xy ∣ |x| = |y|, x ≠ y } is context-free claims that, when x!=y, then it's Context Free. But, how can the letters of x and y be matched on stack? Say x=abbb y=bbbb. How can we say first letters don't match?
Not necessarily restricting ourselves to determinism, will it be even possible by the Context-free Language class (Non-deterministic & Deterministic Pushdown Automata), as a whole, to generate L = {xy | |x| = |y|, x!=y}?
But, a link of Show that { xy ∣ |x| = |y|, x ≠ y } is context-free claims that, when x!=y, then it's Context Free. But, how can the letters of x and y be matched on stack? Say x=abbb y=bbbb. How can we say first letters don't match?
Not necessarily restricting ourselves to determinism, will it be even possible by the Context-free Language class (Non-deterministic & Deterministic Pushdown Automata), as a whole, to generate L = {xy | |x| = |y|, x!=y}?
Solution
There is a big difference between $\{ xy ∣ |x| = |y|, x = y \}$ and $\{ xy ∣ |x| = |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical.
Checking that the first symbol is the same is not difficult. That can easily be achieved with a context-free grammar; we just need a word consisting of some symbol followed by a word with that same symbol in the centre:
$$\begin{align}S&\to a A\mid b B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b \\ \end{align}$$
That doesn't help us with checking that all symbols in the first half are the same as the corresponding symbols in the second half. But it does give us a way to check if some symbol in the first half is the same as the corresponding symbol in the second half:
$$\begin{align}S&\to A A\mid B B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\ \end{align}$$
And clearly it can easily be modified to check whether the corresponding symbols differ, giving the grammar in @Raphael's answer, linked in your question:
$$\begin{align}S&\to A B\mid B A\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\ \end{align}$$
Checking that the first symbol is the same is not difficult. That can easily be achieved with a context-free grammar; we just need a word consisting of some symbol followed by a word with that same symbol in the centre:
$$\begin{align}S&\to a A\mid b B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b \\ \end{align}$$
That doesn't help us with checking that all symbols in the first half are the same as the corresponding symbols in the second half. But it does give us a way to check if some symbol in the first half is the same as the corresponding symbol in the second half:
$$\begin{align}S&\to A A\mid B B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\ \end{align}$$
And clearly it can easily be modified to check whether the corresponding symbols differ, giving the grammar in @Raphael's answer, linked in your question:
$$\begin{align}S&\to A B\mid B A\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\ \end{align}$$
Context
StackExchange Computer Science Q#120491, answer score: 2
Revisions (0)
No revisions yet.