0 votes 0 votes Given language L = (0+1)*0^n, define a DFA with as few states as possible with n > 0. Theory of Computation theory-of-computation finite-automata + – kthegarty asked Apr 30, 2022 kthegarty 372 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Shaik Masthan commented May 1, 2022 reply Follow Share where you stucked while solving it? 0 votes 0 votes nxveen commented Jul 5, 2022 reply Follow Share minimum 2 states needed 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes State = 1 (0+1)*0* = (0+1)* so minimizedDFA has 1 state thedrift611 answered May 3, 2022 thedrift611 comment Share Follow See all 2 Comments See all 2 2 Comments reply r0h17 commented May 20, 2022 reply Follow Share The state can be 2. Because the given language is (0+1)*0^n, here n>0 So, n can be 1,2,3,4 let take n =1; the first smaller string can be 0^1 which is equal to 0. Please correct me if I am wrong. 1 votes 1 votes Hira Thakur commented May 20, 2022 reply Follow Share thedrift611, your regular expression accept $\epsilon$ also but in given regular expression $n>0$ r0h17, $L=(0+1)^*0^n/n>0$. this can be written as $(0+1)^*0^+$minimum length of string is $0$.strings ending with 0’s. $L=(0,00,000…,10,110,1110..010,00110,001100...\infty)$invalid strings are: $(\epsilon,1,11,111,….,01,011,0011,...\infty)$ 0 votes 0 votes Please log in or register to add a comment.