Register

What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?

• retagged by
3,222 views
4 votes
4 votes
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?

A. 8

B. 9

C. 6

D. None
• retagged by
User Avatar

3 Answers

Best answer
10 votes
10 votes

Second last symbol is 1 over {0,1, 2 }

regular expression = (0+1+2)*1(0+1+2).                     Anything Second last Last

For this regular expression NFA is

Convert NFA to DFA

• selected by
User Avatar
1 votes
1 votes

B. 
Whenever the question says the nth symbol from the right side is fixed and the input language has m symbols the answer for minimal dfa is mn  . So 32 = 9

User Avatar
Voting & Accepting an answer helps improve the community

Related questions


Deprecated: Implicit conversion from float-string "1652948649.960" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1652948649.960" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1652948649.960" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1652948649.960" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803

Deprecated: Implicit conversion from float-string "1541472172.998" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 796

Deprecated: Implicit conversion from float-string "1541472172.998" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 801

Deprecated: Implicit conversion from float-string "1541472172.998" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 802

Deprecated: Implicit conversion from float-string "1541472172.998" to int loses precision in /var/www/html/qadb/qa-include/app/format.php on line 803
3.3k
views
2 answers
2 votes
Anurag_s asked Aug 15, 2015
3,268 views
Let Σ= {a}, assume language, L= { a^(2012.K) / K> 0}, what is minimum number of states needed in a DFA to recognize L
Let Σ= {a}, assume language, L= { a^(2012.K) / K 0}, what is minimum number of states needed in a DFA to recognize L
User Avatar
1.3k
views
0 answers
0 votes
koushriek asked May 19, 2022
1,300 views
Number of states in a DFA that accepts the language over the alphabet{0,1} where words start and end with a '1', have even length and where any 0 in the word is immediately followed by at least a 1.
Examples of accepted words: 1011, 101101, 1111Example of non-accepted words: 101, 1001, 010The solution says the min-DFA contains 5 states but I could only do it in 4. Am...
User Avatar
276
views
1 answers
0 votes
Hritik1204 asked Jan 5
276 views
Find the number of final states in DFA that recognizes L, where L= {w1a w2:|w1|≥3,|w2|≤5}, ∑={a, b} and w1, w2 ∈ ∑ * ______
User Avatar
3.0k
views
1 answers
1 votes
sripo asked Nov 6, 2018
2,987 views
What is the minimal DFA for this language (11+111)*, for Σ={0,1}.
What is the number of states for the above DFA,please draw NFA,DFA and minimised DFA for the same.Also won't the language not accept epsilon?
User Avatar
Link Copied!
Total PHP MySQL Other RAM
Time (ms) % Time (ms) % File count Time (ms) % Query count Time (ms) % Amount %
Setup 5.5 3% 4.1 2% 72 1.8 1% 2 0.0 0% 569k 43%
Control 13.2 8% 2.0 1% 5 11.7 7% 12 0.0 0% 269k 20%
View 3.7 2% 3.7 2% 12 0.0 0% 0 0.0 0% 142k 11%
Theme 126.5 81% 5.3 3% 15 121.3 78% 3 0.0 0% 312k 24%
Stats 6.0 3% 0.1 0% 0 6.0 3% 1 0.0 0% 0k 0%
Total 155.0 100% 15.3 9% 104 140.8 90% 18 0.0 0% 1295k 100%