3
$\begingroup$

I got this question on my final exam: Is the following language context-free?

$$ L = \{w\bar w^R \mid w\in \{0,1\}^* \}$$

Notation: The string $\bar w$ is obtained from $w$ by replacing all 0s with 1's and all 1's with 0's. The string $\bar w^R$ is $\bar w$ in reverse order.

I've thought about it being a context-free language, but I notice that when you pump the string in the middle, the string will still be in the language. (using pumping lemma)

I think it's context free. This is the context free grammar:

$$ S \to 0S1 \mid 1S0 \mid \varepsilon $$ (It's basically a palindrome, but both sides are exact opposites.)

Improve this question
$\endgroup$
7
  • $\begingroup$ What do you think? What have you tried to show that it is? Or that it isn't? $\endgroup$
    – Dave Clarke
    Commented Dec 7, 2012 at 6:10
  • $\begingroup$ Ok, i'll show my work $\endgroup$
    – Jessie Love
    Commented Dec 7, 2012 at 6:11
  • 1
    $\begingroup$ Now can you argue (perhaps informally) why your grammar is correct? $\endgroup$
    – Luke Mathieson
    Commented Dec 7, 2012 at 6:14
  • $\begingroup$ alright. i'll add more. done. $\endgroup$
    – Jessie Love
    Commented Dec 7, 2012 at 6:16
  • 4
    $\begingroup$ You are right. Please post your thoughts as self-answer to you question. $\endgroup$
    – A.Schulz
    Commented Dec 7, 2012 at 7:43

1 Answer 1

Reset to default
2
$\begingroup$

A Context free grammer is one in which LHS of atleast one of the productions is free from any terminal symbols (context). According to your production rule,it is clearly CFG.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.