2 votes 2 votes Consider the following regular languages given below: L1 : Languages that accept strings over $\sum \left (a,b \right )$ , such that length of string is greater than $1$, but multiples of $3$. L2 : Languages that accept strings over $\sum \left (a,b \right )$ , such that every string contains at the most $2$ $a' s$ and $2$ $b' s$. L3 : Languages that correspond to following regular expression $R$: $R = 10 + 0 + 11$ $0 * 1$ over $\sum \left ( 0,1 \right )$ Let the number of states in the minimized $DFA$ of each of it be $n1 ,n2 , n3$ respectively. Then, which of the following is TRUE? $n1 = n3 < n2$ $n1 < n3 < n2$ $n3 < n1 < n2$ $n2 < n1 < n3$ GATE tbb-mockgate-3 theory-of-computation finite-automata minimal-state-automata + – Bikram asked Feb 9, 2017 retagged Sep 15, 2020 by ajaysoni1924 Bikram 467 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Harsh181996 commented Mar 13, 2017 reply Follow Share Sir , Solution to the above one please 0 votes 0 votes Bikram commented Mar 13, 2017 reply Follow Share @harsh Draw the DFA's for these three languages and check which option satisfies. 0 votes 0 votes Satyajeet Singh commented Jan 16, 2018 reply Follow Share L2={ ε, a, b, aa, ab, ba,bb} DFA for L2 should have 4 states(including a dead state). Can anyone explain how DFA corresponding to L2 needs 10 states. 0 votes 0 votes jatin khachane 1 commented Jan 1, 2019 reply Follow Share Note: L2 is slight modification of L such that a's are multiple of 3 and b's are multiple of 3 1 votes 1 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes If we draw the DFA for L1 , we will find that it have 4 states = n1 the DFA for L2 , we will find that it have 10 states = n2 the DFA for L3 , we will find that it have 5 states = n3 which clearly satisfies the option B n1 < n3 < n2 Bikram answered Mar 19, 2017 selected Dec 12, 2018 by Manoja Rajalakshmi A Bikram comment Share Follow See all 2 Comments See all 2 2 Comments reply neelesh bhakt commented Dec 16, 2017 reply Follow Share sir please check n3 again it will have 4 states. so option a will be correct 0 votes 0 votes shaurya vardhan commented Jan 1, 2018 reply Follow Share n3 will have 5 states only , you must have forgot to add the dead state ,, i did the same mistake. 1 votes 1 votes Please log in or register to add a comment.