Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Automata theory, regular expressions

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    serbia
    Posts
    3

    Question Automata theory, regular expressions

    Hi,
    I'm having trouble with constructing proof for the following assertions:

    R + S = S + R , commutativity

    (R + S) + T = R + (S + T)
    R (ST) = (RS) T, associativity

    (R+S)T = RT + ST, distributivity

    Where R,S,T are regular expressions. + is the union operation and when there is no operator it indicates concatenation.

    Can anyone give me some guidance?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Automata theory, regular expressions

    This all follows directly from the definition of when a string matches a regular expression. You should consult the precise definition in your source; i'll go from memory. For example, suppose a string w matches (R + S)T. Then w = w1w2 such that w1 matches R + S and w2 matches T. This in turn means that w1 matches either R or S. In the first case, w1w2 matches RT, and in the second case, it matches ST; therefore, w = w1w2 matches RT + ST. Other questions are similar.
    Thanks from leluska
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2013
    From
    serbia
    Posts
    3

    Re: Automata theory, regular expressions

    Thank you. I'll try to figure the rest ones out.
    Although R + S = S + R , commutativity, is still not clear to me. I think that this one can't be proven with your method.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Automata theory, regular expressions

    If w matches R + S, then by definition it matches either R or S. In both cases it matches S + R.
    Thanks from leluska
    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. Help in Theory of Automata
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 05:04 AM
  3. Automata Proof... Theory of Computation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2008, 11:25 PM
  4. Regular Expressions - in Automata
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 28th 2008, 03:49 AM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 17th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum