Results 1 to 2 of 2

Math Help - Regular Expression - need some explaining please.

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    6

    Regular Expression - need some explaining please.

    the grammar below generates the language of regular expression 0*1(0 + 1)*:

    S → A1B
    A → 0A | λ
    B → 0B | 1B | λ

    Give the leftmost and rightmost derivations of the strings:
    (a) 00101
    (b) 1001
    (c) 00011

    Any help would be great, thankyou
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    S → A1B
    A → 0A | λ
    B → 0B | 1B | λ
    (a) 00101
    Well, let's consider the leftmost derivation. We have start with S -> A1B. Since A is at the left, we use its rule. A -> λ does not work since the word would start with 1. Therefore, we apply A -> 0A two times to get 00A1B. After that A disappears to λ. We need 0 after 1, so only the rule B -> 0B works at that point. After that, we use B -> 1B and B -> λ.

    Altogether:

    S -> A1B -> 0A1B -> 00A1B -> 001B -> 0010B -> 00101B -> 00101.

    I hope this is right. If you have concrete difficulties, post them here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Regular Expression (Theory of Automata)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2010, 04:58 AM
  2. Regular expression
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: March 20th 2010, 02:26 PM
  3. regular expression
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: March 16th 2010, 01:30 AM
  4. Regular expression question
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 31st 2009, 06:05 PM
  5. The name of Regular Expression
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2008, 04:50 PM

Search Tags


/mathhelpforum @mathhelpforum