Dfa for odd number of 0 and odd number of 1

By using our site, you acknowledge that you have read and understand our Cookie PolicyPrivacy Policyand our Terms of Service. Stack Overflow for Teams is a private, secure spot for you and your coworkers to find and share information. I want the DFA generation, that will accepts the string having odd number of 1's and odd number of 0's. First, let's build a DFA that accepts an odd number of 0. We need at least one state or else we can't accept anything. That state can't be accepting since the empty string leads there and the empty string doesn't have an odd number of 0.

So, we need at least two states - an initial state that is not accepting, and an accepting state. Do we need more? To answer that question let's start filling in the transitions and see where we get. There must be a transition originating in the accepting state. Where does it go? If it goes to itself, then we don't accept the string 0, which has an odd number one of 0.

So we need to go to some accepting state on 0 in the initial state. We just so happen to have an accepting state already; let's go there. Next, we must have a transition from the accepting state. If we return to the accepting state, we would accept the string 00, so we can't do that.

We must transition to some non-accepting state. We have a non-accepting state already - our initial state - so that choice might work. Alternatively, if not, we must introduce a new state. Let us first consider whether returning to the initial state works, since in that case we are done. We have already reasoned that the strings 0 and 00 are handled correctly. Therefore, this DFA is correct for the language of strings of odd numbers of 0.

The diagram looks like:. To get an automaton accepting strings containing odd numbers of both 0 and 1, imagine running both automata simultaneously: whenever we see a 0, we pass it to the first one, and whenever we see a 1, we pass it to the second one.

Then, we accept if both automata ended up in accepting states. We can represent the combined state of the two automata by considering all four pairs of states from the first and second automata as states of a new, combined automaton, the transitions graph of which looks like this:.

These are the intuitions behind the Myhill-Nerode theorem on regularity of languages and the Cartesian product machine construction for the intersection of regular languages. As DFA accepting odd number of '0's and odd number of '1's. Hope it would help you. Learn more. DFA that will accepts the string having odd number of 1's and odd number of 0's Ask Question. Asked 1 year, 6 months ago. Active 1 year, 6 months ago.By using our site, you acknowledge that you have read and understand our Cookie PolicyPrivacy Policyand our Terms of Service.

Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.

If we use the state removal technique :. Brzozowski Algebraic Method using Arden's Theorem. So after the first 1, you want any other 1s to come in pairs. Sign up to join this community. The best answers are voted up and rise to the top.

Home Questions Tags Users Unanswered. DFA that accepts strings where there are odd number of 1's, and any number of 0's Ask Question. Asked 3 years, 2 months ago. Active 3 years, 2 months ago. Viewed 24k times.

dfa for odd number of 0 and odd number of 1

Active Oldest Votes. S 1, 3 3 gold badges 11 11 silver badges 21 21 bronze badges. Gerry Myerson Gerry Myerson k 11 11 gold badges silver badges bronze badges. Sign up or log in Sign up using Google. Sign up using Facebook. Sign up using Email and Password. Post as a guest Name. Email Required, but never shown. Featured on Meta. Responding to the Lavender Letter and commitments moving forward.

Related 1. Hot Network Questions. Question feed. Mathematics Stack Exchange works best with JavaScript enabled.By using our site, you acknowledge that you have read and understand our Cookie PolicyPrivacy Policyand our Terms of Service. Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.

Want to design a DFA that accept all strings with odd number of 0's and odd number of 1's is it possible?

Subscribe to RSS

Sign up to join this community. The best answers are voted up and rise to the top. Home Questions Tags Users Unanswered. Dfa accepting all strings with odd number of 0's and odd number of 1's Ask Question.

Asked 3 years ago. Active 3 years ago. Viewed 3k times. Mohammad Umer Mohammad Umer 1 1 1 silver badge 2 2 bronze badges. Pin Sep 30 '17 at Is this a hint enough? Active Oldest Votes. Sign up or log in Sign up using Google. Sign up using Facebook. Sign up using Email and Password. Post as a guest Name. Email Required, but never shown.

Featured on Meta. Responding to the Lavender Letter and commitments moving forward. Related 2. Hot Network Questions. Question feed. Mathematics Stack Exchange works best with JavaScript enabled.By using our site, you acknowledge that you have read and understand our Cookie PolicyPrivacy Policyand our Terms of Service.

Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science.

DFA in LEX code which accepts Odd number of 0’s and even number of 1’s

It only takes a minute to sign up. But 1wont be accepted. I believe your language is not regular and if I'm not mistaken, the pumping lemma suffices: Let us assume by contradiction your language is regular, thus it should hold all 3 conditions of the pumping lemma. For more information: pumping lemma. Sign up to join this community. The best answers are voted up and rise to the top. DFA for strings with number of 0's odd only in substring longer than 1 Ask Question.

Asked 2 years, 3 months ago. Active 2 years, 1 month ago. Viewed times. Xhark Xhark 3 3 bronze badges. Active Oldest Votes. You can try using a TM.

Reckless Engineer Reckless Engineer 16 2 2 bronze badges. However, for this is simply an example, I'll edit the answer to emphasize that. Regardless, for such a word, we could always then make the number of 0s be even using pumping. Sign up or log in Sign up using Google. Sign up using Facebook. Sign up using Email and Password. Post as a guest Name.

Even Even and ODD ODD language regular expression- Theory of Automata Full Course Lecture 43

Email Required, but never shown. Featured on Meta. Responding to the Lavender Letter and commitments moving forward. Linked Related 3. Hot Network Questions. Question feed.By using our site, you acknowledge that you have read and understand our Cookie PolicyPrivacy Policyand our Terms of Service.

Stack Overflow for Teams is a private, secure spot for you and your coworkers to find and share information. I've tried this a few different ways but I can't seem to get it right.

Ignore the below diagram as it was a try gone wrong. The problem with my DFA is that for example when I enter into it it shouldn't be accepted but it is. And with it isn't accepted when it should be.

dfa for odd number of 0 and odd number of 1

Not quite sure how to fix this. Firstly you can make all the states possible in the DFA itself. These are : - even 1's and even 0's - even 1's and odd 0's - odd 1's and odd 0's - odd 1's and even 0's. Give them some relevant names so that they can be easily identified. What we need in this question is even 0's and odd 1's. So the second state is the Final state.

Also keep in mind that at first when there's no input i. That is the first state. Learn more. DFA that accepts even number of 0's and odd number of 1's Ask Question. Asked 3 years, 10 months ago. Active 6 months ago. Viewed 4k times. Thanks for your help! Jack Timber Jack Timber 45 1 1 silver badge 5 5 bronze badges. Active Oldest Votes.

dfa for odd number of 0 and odd number of 1

I would start by thinking about designing an automata that: accepts the simplest possible string it should accept: "1" and rejects the simplest possible string that it should reject: "". Thanks for your help, got the answer now I think! Here are a couple of hints that you may find helpful. First, design a DFA that accepts the set of all strings with an even number of 0s.The FA will have a start state q0 from which only the edge with input 1 will go to the next state.

In state q1, if we read 1, we will be in state q1, but if we read 0 at state q1, we will reach to state q2 which is the final state. In state q2, if we read either 0 or 1, we will go to q2 state or q1 state respectively. Note that if the input ends with 0, it will be in the final state.

In the given solution, we can see that only input will be accepted. Hence, for inputthere is no other path shown for other input.

Here q0 is a start state and the final state also. Note carefully that a symmetry of 0's and 1's is maintained. We can associate meanings to each state as:.

Examples of DFA

The strings that will be generated for this particular languages are, The transition graph is as follows:. The stages q0, q1, q2 are the final states. The DFA will generate the strings that do not contain consecutive 1's like 10, JavaTpoint offers too many high quality services. Mail us on hr javatpoint. Please mail your requirement at hr javatpoint. Duration: 1 week to 2 week. Automata Tutorial. Next Topic NFA. Verbal A. Angular 7. Compiler D. Software E. Web Tech.

Cyber Sec. Control S. Data Mining. Javatpoint Services JavaTpoint offers too many high quality services. Solution: The FA will have a start state q0 from which only the edge with input 1 will go to the next state.

Solution: In the given solution, we can see that only input will be accepted.To merge these two machines, we will take the Cartesian product of the states of these two machines:. Initial state of these DFA will be the state which contains the initial states of those two separate machines.

As, q0 and q2 are the initial states thus, q0q2 is the initial state of the final DFA. This machine accept that languages which contains either odd no. As we know that q1 indicates odd no. So, the final states of the required DFA will contain either q1 or q2. This is our required DFA which accept the languages containing odd no. This machine accept that languages which contains odd no. So, the final states of the required DFA will contain both q1 and q2.

So, the final states of the required DFA will contain exactly one among q1 and q2. Attention reader!

DFA machines accepting odd number of 0’s or/and even number of 1’s

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below. Writing code in comment? Please use ide. Check out this Author's contributed articles.

Load Comments. We use cookies to ensure you have the best browsing experience on our website.


Posts created 1

thoughts on “Dfa for odd number of 0 and odd number of 1

Leave a Reply

Your email address will not be published. Required fields are marked *

Begin typing your search term above and press enter to search. Press ESC to cancel.

Back To Top