Results 1 to 9 of 9

Math Help - Finding a CFG that generates the following language

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Finding a CFG that generates the following language

    I am trying to find a CFG that generates the following language : \overline{\{ ww^R \mid w \in \Sigma^*\}}.

    I am not sure how to approach this. Can someone help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Say there are only 2 letters; a and b. Then we would have

    S → T
    T → aTa | bTb | aNb | bNa | a | b
    N → aNb | bNa | aNa | bNb | a | b | \epsilon

    Can you generalize for all alphabets ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    I was hoping you didn't give me the answer. Its my fault. I should have said it explicitly. Now its hard for me not to look. I was doing something like so :

    Let Σ={a1,a2,…,an}, then the following CFG accepts S.

    Q→A1 | B2
    A1 → a1 A1 a1 | a2 A1 a2 |…| an A1 an | ϵ | A2
    A2 → something goes here and possibly more

    Now lets see If I understand. T is forced to make any string of the form ww^r to end with something different then what it starts out with.
    And N's purpose is just to enable different types of strings? So in general it would be something like so:

    Let Σ={a1,a2,…,an}, then the following CFG accepts S.

    S → T
    T → a1Ta2 | ... | anTan | U | V
    U → a1 | ... | an
    V → aiXaj ; where i != j
    X → ϵ | U | aiXaj ; where 0 < i,j <= n

    Is that sufficient? I tried to separate the steps to make it easier to read and write.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Small typo, you meant T → a1Ta1.

    The rest is fine.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    So this is what I came up with. I've been known to make typos. Can you check it :


    The set S5 =compliment of { ww^R |w \in \Sigma^*} is context–free. We construct a CFG to prove this proposition.
    Let Σ={ a_1,a_2,…,a_n}, and let 0<i,j≤|Σ| then the following CFG accepts S5.
    Q→ T
    T→ a_i Ta_j  | U |  V ; i=j
    U→ a_i
    V→ a_i Va_j  | U |\epsilon
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    No this is wrong. For example, T → a1Ta1 → a1Va1 → a1ea1 → a1a1 is valid here ( e stands for epsilon ).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Oh I see, how about this

    The set S5 =compliment of { ww^R |w \in \Sigma^*} is context–free. We construct a CFG to prove this proposition.
    Let Σ={ a_1,a_2,…,a_n}, and let 0<i,j,k,l≤|Σ| then the following CFG accepts S5.
    Q→ T
    T→ a_i Ta_j  | U |  a_k V a_l ; i=j and k != l
    U→ a_i
    V→ a_i Va_j  | U |\epsilon

    the only new thing added was k and l, and a_k and a_l
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Seems alright to me
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Thanks a lot. You guys are really so much help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: December 23rd 2010, 10:57 AM
  2. Prove that a group of tensors generates a Lie algebra
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: June 20th 2010, 10:33 AM
  3. Automorphisms, if it generates a group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 16th 2009, 05:10 AM
  4. Econ: rational preference relation generates nonempty choice rule
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: September 8th 2009, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum