![]() With practice you can draw the DFA directly without having to make any tables. If you can follow this first-principles DFA logic, it is faster than writing two DFAs and making their cross product. ![]() If you add another a, then where? Back to 0a1b (because number of a’s follows the mod2 cycle and technically you have only read 1mod3 b’s so far, so no change in b’s). If you add an a here, where do you go? 1a1b. For example, from 0a0b, use an a to go to 1a0b, and then one more a to go back to 0a0b. In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. The first state, 0a’s 0b’s is the initial as well as the final state (since we want the input to have number of a’s divisible by 2 and number of b’s divisible by 3).ĭraw the states and then figuring out the transitions is easy. Theory of computation and compiler design are the good scoring subject in the Gate exam, we are going to provide in-detail analysis and all the questions are arranged in topic wises As all, we know Practice makes a man perfect, so practicing all the below Theory of Computation Questions will help in your gate exam to get a good rank. ![]() The number of rows gives us the number of states in the DFA, and this is the minimum (you can verify using Myhill-Nerode). First make a table of number of a’s and b’s. For those looking for a way other than cross product, use state labeling.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |