Results 1 to 5 of 5

Math Help - Verify me answer please

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Verify me answer please

    So the question: Any regular language is context-free

    So here is my proof by construction :

    Let M=(Q,Σ,δ,q_0,F) be some DFA that accepts a regular language L. We construct a grammar G=(V,Σ,R,S) such that L(G)= L(M) as follows:

    V={ X_q | q ∈ Q }
    S= X_q0  ;where q_0 is the start symbol of M

    R = R_1 R_2 where
    R_1= X_q→ ϵ iff δ(q,a) = f,where f∈F}
    R={ X_q→a X_r  iff δ(q,a)= r }

    The above construction works because if the DFA goes from a state q_i to a state q_j for an input x∈Σ then the CFG does something similar. That is, the CFG generates x and the goes onto the next variable that is, it X_i generates xX_j thus effectively, going to the next variable. We also add a rule the handle accepting states, that is if q_k goes to the state q_l where q_l∈F, then our CFG just terminates outputting epsilon. So we see that our CFG generates the input read from the DFA M, thusL(G)= L(M).



    Is the construction correct? Is the above explanation sufficient to show that the construction is correct? Please check it for technical loop holes. Thanks for helping me again. Seems like your the only one that knows their stuff
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Your construction is correct. I have only one remark.
    Quote Originally Posted by Matter_Math View Post
    R = R_1 R_2 where
    R_1= X_q→ ϵ iff δ(q,a) = f,where f∈F}
    R={ X_q→a X_r  iff δ(q,a)= r }
    The rule X_q → ϵ does not generate any terminal symbol while the transition from q to f reads the symbol a. You should have either X_q → a or X_f → ϵ where f is an accepting state. The second variant is better because it accounts for the case when there is an empty word in the language. And, of course, the second part of R should be labeled R_2 above.

    Whether this explanation is sufficient depends on the requirements of your course. To be strict, one has to have an argument by induction on the length of the word. For this, one has to generalize the statement "A word is accepted by the automaton iff it is generated by the grammar" to describe the intermediate situation, when only a part of the word has been read and generated. It's a good exercise to formulate such general induction statement; after that, the base case and the step are pretty obvious.

    Note that the grammar you constructed is called a right regular grammar.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Thanks for the help. The professor is pretty strict. I will try to do induction to its length. Thanks again. I'll post back soon.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Hey I'm stuck. Can you help me. Not sure how to start after thinking about it a little bit.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    The induction statement P(n) is: "For every word w of length n in \Sigma^*, the automaton is in state q after reading w iff the grammar generates w X_q". Then from "for all n, P(n)" one can derive "A word w in \Sigma^* is accepted by the automaton iff it is generated by the grammar".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Please verify answer on this set question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 20th 2011, 09:08 AM
  2. Finding an. Verify my answer.
    Posted in the Calculus Forum
    Replies: 4
    Last Post: September 29th 2011, 01:11 PM
  3. Finding the sum, verify my answer please.
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 26th 2011, 12:14 AM
  4. Verify answer please
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 20th 2010, 03:58 PM
  5. I want to verify my answer
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 17th 2009, 09:50 PM

Search Tags


/mathhelpforum @mathhelpforum