Results 1 to 5 of 5

Thread: Automata Theory regular expressions

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    8

    Automata Theory regular expressions

    hello , hopefully i made this post in the right section lol. im trying to brush up on my automata for a test and i ran into something thats confusing me. this question asks

    Which of the following regular expressions denotes the set of all strings over the alphabet {0,1} that contains at least one 0.
    a) (1+0)*0(1+0)*
    b) (1+0)*01*
    c) 1*0(1+0)*
    d) (1+0)*00*
    e) 0*0(1+0)*
    f) 1*00*
    g) 0

    now from what im seeing doesnt everyone of these choices contain atleast 1 zero? i dont know if maybe im reading the question wrong . i understand how to read the * and + but im not quite understanding what its asking. like for a) u can get 0 by itself, so thats atleast 1 zero. for b) u can get 0 alone, thats also atleast 1 zero.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,608
    Thanks
    1714

    Re: Automata Theory regular expressions

    Hey zerocool18.

    Does this mean the string is forced to have a 0 anywhere or in a specific way?

    Looking at the question I'm inclined to agree with you but I should ask anyway.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    8

    Re: Automata Theory regular expressions

    Quote Originally Posted by chiro View Post
    Hey zerocool18.

    Does this mean the string is forced to have a 0 anywhere or in a specific way?

    Looking at the question I'm inclined to agree with you but I should ask anyway.
    thats exactly how the question is worded. so im assuming that it can be anywere
    Last edited by zerocool18; Mar 30th 2016 at 11:24 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,608
    Thanks
    1714

    Re: Automata Theory regular expressions

    I thought so but I had to clarify.

    Based on what you have stated every expression should have at least one zero (some many more).

    I'm not sure how you could prove it but you could break up the strings in sub-strings and show them as a union of 0 terms and other arbitrary terms thus completing some sort of formal proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    8

    Re: Automata Theory regular expressions

    Quote Originally Posted by chiro View Post
    I thought so but I had to clarify.

    Based on what you have stated every expression should have at least one zero (some many more).

    I'm not sure how you could prove it but you could break up the strings in sub-strings and show them as a union of 0 terms and other arbitrary terms thus completing some sort of formal proof.
    thanks i appreciate the help , atleast i know im on the right track lol
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata theory, regular expressions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 25th 2013, 04:48 AM
  2. Regular Expression (Theory of Automata)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2010, 04:58 AM
  3. Help in Theory of Automata
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 10th 2009, 05:04 AM
  4. Regular Expressions - in Automata
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Feb 28th 2008, 03:49 AM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 17th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum