Re: A CFG for a CFL

From: Michael J. Fromberger (Michael.J.Fromberger_at_Clothing.Dartmouth.EDU)
Date: 04/25/04 

Date: Sun, 25 Apr 2004 08:56:15 -0400

In article <408B5D49.72FE5433@msgid.michael.mendelsohn.de>,
 Michael Mendelsohn <keine.Werbung.1300@msgid.michael.mendelsohn.de>
 wrote:

> Bilal Sallakh schrieb:
> > The language
> > L = {x: x = w.w} is not a CFL, easily using the pumping lemma.
>
> This is not correct.
> It's not a regular Language, but it _is_ a context-free language.

Unfortunately, that is not correct: You are right, that L is not
regular, but for a given alphabet A, if |A| > 1 then the language
  L = { wcw | w, c in A* }
is also not context-free. This is a common example used to demonstrate
the pumping lemma for CFL's. There is a pathological case where in
which L is a CFL when |A| = 1, but in that case, L is also regular
(odd-length strings and epsilon match).

> > However I found an elegant solution on the Stanford website:
> >
> > S -> AB | BA | A | B
> > A -> aAa | aAb | bAa | bAb
> > B -> aBa | aBb | bBa | bBb
>
> [...]
>
> Maybe I misunderstand your requirement:
> > L = {x: x is not of the form w.w : w in (0+1)*}
> You want a CFL over the alphabet {0,1}
> that contains no words x of the form x=w.w , right?

I believe that is the original poster's language, yes.

-M 

-- 
Michael J. Fromberger             | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/  | Dartmouth College, Hanover, NH, USA

Relevant Pages

  • Re: Armenian, Sumerian, Burushaski, and Turkic languages
    ... indicating the importance of finding regular changes. ... There are certainly plenty of known regular correspondences ... Note that due to sporadic language change, ... sound changes, large variance in what counts as "similar"), you're ...
    (sci.lang)
  • Re: pumping lemma for CFL
    ... >> resulting string is in L. ... > not the regular language version. ... yes i am wanting to understnad the CFL pumping lemma exists string in L ...
    (sci.math)
  • Re: Perl HTML searching
    ... My initial reaction would be something like - I'm pretty sure *any* method, including the use of HTML::LinkExtor, or XML transform, involves using regular expressions "for the purposes of parsing HTML". ... But unless your language is a regular language (and there aren't many ...
    (comp.lang.perl.misc)
  • Re: American as creolish [was] Re: Baltic Is Gothic
    ... > language and language evolution. ... Forming "regular" preterits, participles, and plurals in English ... > introduces redundancy with formal tokens. ... expressions became "normal", driving out the old expressions with no ...
    (sci.lang)
  • Re: RegExp as Finite State Machine
    ... but not regular, if I'm not mistaken -- with the Regular Expression ... The language recognized by the regexp above is actually not even ... If all Javascript regexps can be implemented using only finite state ... subset of Finite State Machines. ...
    (comp.lang.javascript)