Re: Is this language context free?

I am sorry. I have no idea why the characters are displayed incorrectly.

The language L = {xyz | x = y^R, z is a string with only c's, and x != z}
Here y^R denotes the string obtained by reversing y.

Thanks,
Dillon


"Chris Smith" <cdsmith@xxxxxxxxx> wrote in message
news:02c579b7$0$2358$c3e8da3@xxxxxxxxxxxxxxxxxxxx
Dillon wrote:
This is a problem I have been working on for a while:

Consider the following language L over the alphabet {a, b, c}. L = {xyz
| x = y^R, z is a string with only c's, and lx|?¨´ lzl }. Here y^R
denotes the string obtained by reversing y.

Is L context free?

You seem to have some corruption in your notation there. What does
"lx|?¨´ lzl" mean? Can you explain it in words?

Without that unknown condition, this language is trivially context-free.

--
Chris Smith


.

Relevant Pages

  • Re: Is this language context free?
    ... denotes the string obtained by reversing y. ... Is L context free? ... this language is trivially context-free. ...
    (comp.theory)
  • Re: boolean endsWith(String s, Pattern pattern)
    ... > I am talking about reversing regexes expressed in the language supported ... ambiguous "parses". ... reluctant never changes the language that the regexp recognises, ...
    (comp.lang.java.programmer)
  • Differential-Form Version of (div grad) V = curl curl V + grad div V
    ... where (div grad) denotes the Laplacian operator. ... What is the equivalent of this identity in the language of ...
    (sci.physics)
  • Re: question about categoricity
    ... >> but since Chris's example involves expanding the language of the first ... > denotes i in B, for all i, and nothing denotes you in B." ... but i'm just not sure where this technique would fail in this case? ...
    (sci.logic)
  • Re: Win key and alt key
    ... Now the keys are correctly mapped. ... why it was happening before I tried reversing it with software. ... Perhaps you are have it set for a language ... that doesn't match the physical keyboard. ...
    (microsoft.public.windowsxp.general)