Re: Is this language context free?

Dillon wrote:
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.

Yes, it is context-free. It turns out this is the same as L' =
{ xyz | x = y^R, z contains only c's }. Here's why they are the same
language.

First, that w in L implies w in L' is obvious, since L is a subset of L'
by adding the additional condition. So the remaining task is to show
that if w is in L', then w is also in L.

There are two cases. In case #1, the input string does not contain all
'c' characters. Then if w is in L', then take the division into w = xyz
that must exist because w is in L'. Observe that x must contain a
non-'c' character; otherwise, there would be all 'c' characters in w. So
clearly x != z, so w = xyz satisfies all the conditions of L. Therefore,
w is in L. In case #2, w consists of all 'c' characters. Then let x and
y both be the empty string, and z = w. Then w = xyz, and all the
conditions of L are satisfied.

(I interpreted "contains only c's" to mean that z must contain at least
one 'c'. If you allow z to be empty, then the two languages will differ
on the empty string.)

So since L = L', the context-free grammar for L, which is trivial to
write down, also suffices for L'.

--
Chris Smith
.

Relevant Pages

  • RE: VBA question: How to extract cell values in different language
    ... language is entered, but it seems like all that data is lost when the VBA ... about having binary data and not unicode data confirms my suspicions. ... You are have 256 binary characters. ... First column has the string IDs ...
    (microsoft.public.excel.programming)
  • Re: Russian language support
    ... Actually in our previous test we didnt do language transition properly ... bytes, or if in Unicode, just a string of 2-byte values, each of which is ... it selects a font to use to display ... TTF fonts in Windows CE map Unicode characters into suitable glyphs. ...
    (microsoft.public.windowsce.platbuilder)
  • RE: VBA question: How to extract cell values in different language
    ... language is entered, but it seems like all that data is lost when the VBA ... You are have 256 binary characters. ... Unicode data on the same file with two diffferent language setting gives you ... First column has the string IDs ...
    (microsoft.public.excel.programming)
  • RE: VBA question: How to extract cell values in different language
    ... You are have 256 binary characters. ... Depending on the language settings the characters are displayed differrently, ... Unicode data on the same file with two diffferent language setting gives you ... First column has the string IDs ...
    (microsoft.public.excel.programming)
  • Re: How to convert Infix notation to postfix notation
    ... If this is for an error message, why isn't it using stderr for its output? ... array of 15 characters, and you call this function with the limit 15 on ... Making sure that the only string I allocate and append to, ... because mulFactor in all versions must needs incorporate the functions ...
    (comp.lang.c)