Facebook Page
Twitter
RSS
+ Reply to Thread
Page 1 of 5 123 ... LastLast
Results 1 to 10 of 44
  1. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Online
    Join Date
    Apr 2013
    Posts
    3,096
    Thanks
    3,062 times
    Thanked
    954 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #1
    Hello!!!

    I want to construct a dfa that recognizes the language $((0 \cup 1)^{\ast} 1 0^{\ast}) \cup 0$.

    I have thought of the following NFA:



    But I am facing difficulties on converting this to a NFA. Could you give me a hint how we could do this?

  2. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    5,805
    Thanks
    3,893 times
    Thanked
    11,043 times
    Thank/Post
    1.902
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #2
    Quote Originally Posted by evinda View Post
    Hello!!!

    I want to construct a dfa that recognizes the language $((0 \cup 1)^{\ast} 1 0^{\ast}) \cup 0$.

    I have thought of the following NFA:



    But I am facing difficulties on converting this to a NFA. Could you give me a hint how we could do this?
    Hey evinda!!

    Once we've started recognizing $(0 \cup 1)^{\ast}$, we're too late to match the $0$ at the end.
    As it is now we might match for instance $00$, which is not supposed to be accepted.

    So I think we need to split the first state into 2 states, and put a new start state before them.
    One for the $(0 \cup 1)^{\ast}$ part, and another for the $0$-at-the-end part.

  3. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Online
    Join Date
    Apr 2013
    Posts
    3,096
    Thanks
    3,062 times
    Thanked
    954 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #3 Thread Author
    Quote Originally Posted by I like Serena View Post
    Hey evinda!!

    Once we've started recognizing $(0 \cup 1)^{\ast}$, we're too late to match the $0$ at the end.
    As it is now we might match for instance $00$, which is not supposed to be accepted.

    So I think we need to split the first state into 2 states, and put a new start state before them.
    One for the $(0 \cup 1)^{\ast}$ part, and another for the $0$-at-the-end part.
    So you mean that the following nfa would recognize the language?


  4. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    5,805
    Thanks
    3,893 times
    Thanked
    11,043 times
    Thank/Post
    1.902
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #4
    Quote Originally Posted by evinda View Post
    So you mean that the following nfa would recognize the language?
    Yep.

  5. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Online
    Join Date
    Apr 2013
    Posts
    3,096
    Thanks
    3,062 times
    Thanked
    954 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #5 Thread Author
    Quote Originally Posted by I like Serena View Post
    Yep.
    And how can we convert this to a dfa?

  6. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    5,805
    Thanks
    3,893 times
    Thanked
    11,043 times
    Thank/Post
    1.902
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #6
    Quote Originally Posted by evinda View Post
    And how can we convert this to a dfa?
    How about following the procedure to make such a conversion?

  7. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    5,805
    Thanks
    3,893 times
    Thanked
    11,043 times
    Thank/Post
    1.902
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #7
    We should label each of the states with, say, $q_0, q_1, q_2, q_3$.
    Then we'll create new states, starting with the starting state.
    From there we need to create a new state that is associated with the set of states we can reach when we read $0$.
    And another state that is associated with the set of states we can reach when we read $1$.
    After that we should repeat until we have our DFA.

    So the first new state is $Q_0=\{q_0\}$.
    From there we get $Q_1=\{q_1, q_3\}$ that we can reach with $0$.
    And $Q_2=\{q_1, q_2\}$ that we can reach with $1$.

  8. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Online
    Join Date
    Apr 2013
    Posts
    3,096
    Thanks
    3,062 times
    Thanked
    954 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #8 Thread Author
    Quote Originally Posted by I like Serena View Post
    We should label each of the states with, say, $q_0, q_1, q_2, q_3$.
    Then we'll create new states, starting with the starting state.
    From there we need to create a new state that is associated with the set of states we can reach when we read $0$.
    And another state that is associated with the set of states we can reach when we read $1$.
    After that we should repeat until we have our DFA.

    So the first new state is $Q_0=\{q_0\}$.
    From there we get $Q_1=\{q_1, q_3\}$ that we can reach with $0$.
    And $Q_2=\{q_1, q_2\}$ that we can reach with $1$.
    We can reach $q_2$ after having read $\epsilon, 0 \text{ or } 1$ and $1$.
    Why is it included at $Q_2$ ? So doesn't it contain all the states that could be reached after having read once $1$ ?

    Then, do we set as $Q_3$ the set of states that can be reached from $q_1$ or $q_3$ by reading 0 and as $Q_4$ the set of states that can be reached from $q_1$ or $q_2$ by reading 1?

    Or have I understood it wrong?

  9. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Online
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    5,805
    Thanks
    3,893 times
    Thanked
    11,043 times
    Thank/Post
    1.902
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #9
    Quote Originally Posted by evinda View Post
    We can reach $q_2$ after having read $\epsilon, 0 \text{ or } 1$ and $1$.
    Why is it included at $Q_2$ ? So doesn't it contain all the states that could be reached after having read once $1$ ?
    We can also reach $q_2$ after $\epsilon, 1$, without reading a $0$ or $1$ in between.


    Quote Quote:
    Then, do we set as $Q_3$ the set of states that can be reached from $q_1$ or $q_3$ by reading 0 and as $Q_4$ the set of states that can be reached from $q_1$ or $q_2$ by reading 1?

    Or have I understood it wrong?
    First off, $Q_2$ should be a final state, since we can stop there.
    And indeed, $Q_3$ would be the state after reading $0$ from $Q_1$ representing $q_1$ or $q_3$.
    Logically $Q_4$ would be the state after reading $1$ from $Q_1$ representing $q_1$ or $q_3$.
    And $Q_5, Q_6$ after reading $0$ respectively $1$ from $Q_2$ representing $q_1$ or $q_2$.

    When we define $Q_2,Q_3,Q_4,Q_5$, we can see if we can merge some of them without losing anything.

  10. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Online
    Join Date
    Apr 2013
    Posts
    3,096
    Thanks
    3,062 times
    Thanked
    954 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #10 Thread Author
    Quote Originally Posted by I like Serena View Post
    We can also reach $q_2$ after $\epsilon, 1$, without reading a $0$ or $1$ in between.
    Oh yes, that's right...

    Quote Originally Posted by I like Serena View Post
    First off, $Q_2$ should be a final state, since we can stop there.
    And indeed, $Q_3$ would be the state after reading $0$ from $Q_1$ representing $q_1$ or $q_3$.
    Logically $Q_4$ would be the state after reading $1$ from $Q_1$ representing $q_1$ or $q_3$.
    And $Q_5, Q_6$ after reading $0$ respectively $1$ from $Q_2$ representing $q_1$ or $q_2$.

    When we define $Q_2,Q_3,Q_4,Q_5$, we can see if we can merge some of them without losing anything.

    So we have the following, right?

    $$Q_0=\{q_0\} \\ Q_1=\{ q_1, q_3\} \\ Q_2=\{ q_1, q_2\} \\ Q_3= \{ q_1 \} \\ Q_4=\{ q_1, q_2\} \\ Q_5=\{ q_1, q_2\} \\ Q_6=\{ q_1, q_2\}$$

    How can we check if we can merge some of the states without losing anything?

Similar Threads

  1. Replies: 3
    Last Post: September 21st, 2014, 16:51
  2. [SOLVED] P(X-x) find P, find X, from table
    By karush in forum Basic Probability and Statistics
    Replies: 10
    Last Post: August 2nd, 2013, 16:44
  3. Find polynomials in S, then find basis for ideal (S)
    By rapid in forum Linear and Abstract Algebra
    Replies: 3
    Last Post: May 5th, 2012, 03:44

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards