Menu
I'd really love your help with this deciding whether the language of all words over the alphabet {0,1} that can't be read from both sides the same way, { w | w <> wR }, is a context-free language (that is, it can be transformed into specific grammar rules).
I tried to prove that it is not a context-free language by the pumping lemma, but I didn't find a string which will lead me to contradiction.
Any suggestions?
870
Example 2: L2 = { wwr| w {a, b }+ } is a context-free language , where w is a non-empty string and wr denotes the reversal of string w, that is, w is spelled backward to obtain wr .
A grammar is context-free if left-hand sides of all productions contain exactly one non-terminal symbol. By definition, if one exists, then the language is context-free.
An expression that doesn't form a pattern on which linear comparison could be carried out using stack is not context free language. Example 1 – L = { a^m b^n^2 } is not context free. Example 2 – L = { a^n b^2^n } is not context free.
It's a context sensitive language. wwr is context free because you can use a pda to compare the first alphabet of wr with the last alphabet of w.
If I'm reading your question correctly, you're looking to see if the set of non-palindromes is a context free language.
It is a context free language:
S --> 0S0 | 1S1 | R
R --> 0V1 | 1V0
V --> 0V0 | 1V1 | R | 1 | 0 | ε
Starting at S, the notion is to build the string from the outside in. S allows you to place as many matching ones or zeroes as you want (possibly none) until you reach a case of R in which there is a non-match. From there on you can place either matches or non-matches (because at this point we're already guaranteed to not be a palindrome.) This is sufficient to describe all non-palindromes -- from outside to in, they start with zero or more matching pairs, then one mismatching pair, and then zero or more pairs (matching or not). Finally, there may or may not be a character in the middle.
P.S. If you don't already have it, Sipser's book on Theory of Computation is undoubtedly excellent. In fact, it's the only college book I still read from time to time.
128
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
