Context-free grammar

Page 1 of 1

6 Replies - 6124 Views - Last Post: 02 July 2010 - 10:39 AM

#1 Apprentice123   User is offline

  • D.I.C Regular

Reputation: -16
  • View blog
  • Posts: 265
  • Joined: 30-June 08

Context-free grammar

Posted 27 June 2010 - 06:17 PM

Develop context-free grammars that generate languages:

L1 = {w|w is palindrome in {a,b}^* , w=w^*}
L2 = {ww^* | w is word of {a,b}^*}


My attempt
1)
S -> aSa | bSb | E | a | b
E is empty
Correct ?

2) I could not. Any tips?
Is This A Good Question/Topic? 0
  • +

Replies To: Context-free grammar

#2 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Context-free grammar

Posted 30 June 2010 - 11:41 AM

the first grammar is correct

the second language, i don't really think its a context free language, I think its in the next level of the hierarchy, needs a Turing machine to be able to recognize it, or maybe you just didn't write it correctly, i could be wrong though.
Was This Post Helpful? 0
  • +
  • -

#3 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Context-free grammar

Posted 30 June 2010 - 11:55 AM

actually i am pretty sure that the language ww^* is not context free. you can't design a CFG or a pda that would regonize a string that is concatenated to itself.
Was This Post Helpful? 0
  • +
  • -

#4 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 885
  • Joined: 27-June 09

Re: Context-free grammar

Posted 01 July 2010 - 09:54 AM

Doesn't w^* mean w repeated any number of times (even zero times)? Thus isn't ww^* just all non-empty strings over {a,b}^*?
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Garr*


Reputation:

Re: Context-free grammar

Posted 01 July 2010 - 01:38 PM

Mojo666, that is correct.

Mostyfriedman, you probably looked at Sipser and saw his example of "ww" not being context-free. True, but "ww*" is different. So, as Mojo pointed out, it's trivial to show that:

L2 = {ww^* | w is word of {a,b}^*} = {v | v is a word of {a,b}^*}

Obviously it's context-free.
Was This Post Helpful? 0

#6 Guest_Garr*


Reputation:

Re: Context-free grammar

Posted 01 July 2010 - 01:54 PM

Just a small correction. Mojo666, empty strings, should be fine too.
Was This Post Helpful? 0

#7 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Context-free grammar

Posted 02 July 2010 - 10:39 AM

actually you guys are correct. it is context free.
Was This Post Helpful? 1
  • +
  • -
Page 1 of 1