Results 1 to 8 of 8

Math Help - Is this grammar proof correct, check please?

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Is this grammar proof correct, check please?

    Prove that the following languages are context-free by giving grammars that accept them
    \{ ww^R \mid w \in \Sigma^*\}

    I am not sure if this valid, but this is my proof :

    The set S = \{ ww^R \mid w \in \Sigma^*\}} is context –free. We construct a CFG to prove this proposition.
    Let Σ={ {a_1,a_2,…, a_n}}, then the following CFG accepts S.

    S→ A_1 | A_2 |…|  A_n | ϵ
    A_1 a_1 Ta_1 | a_1 a_1
    A_2 a_1 Ta_2 | a_2 a_2

    A_n a_n Ta_n | a_n a_n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    What happens to the T ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Sorry, the "S->" should be "T->"
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    In general, we keep the starting symbol separate from all other symbols. Your grammar is alright, but it could have been much shorter.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    what do you mean? I guess I could add an extra level of indirection. Does the above grammar accept the set S? Can you show some ways then to improve my grammar please?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    S→ T
    T → a_1Ta_1 | a_2Ta_2 | .... | a_nTa_n | \epsilon
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    oh i see, thanks
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Hey, so there is another problem where I have to show that the complement of the above set, is also recognized by some CFG. I am kind of stuck trying to come up with some proof. Can you provide some hints or some idea on how to go about this construction. Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof Please: Context Free Grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2011, 07:10 PM
  2. Please help to check whether my ODE is correct
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: April 17th 2010, 09:18 PM
  3. Need to check if what i got is correct or no
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 6th 2010, 12:48 AM
  4. please check if my proof is correct
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 6th 2009, 08:02 PM
  5. [SOLVED] Please check if correct
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: October 30th 2008, 03:44 PM

Search Tags


/mathhelpforum @mathhelpforum