Register

Recent questions tagged finite-automata

7 votes
5 answers
181
ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is $3$ $4$ $5$ $6$
Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is$3$$4$$5$$6$
User Avatar
0 votes
0 answers
184
Michael Sipser Edition 3 Exercise 4 Question 27 (Page No. 212)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 votes
1 answer
185
Michael Sipser Edition 3 Exercise 4 Question 26 (Page No. 212)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 votes
0 answers
188
Michael Sipser Edition 3 Exercise 4 Question 17 (Page No. 212)
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
User Avatar
0 votes
0 answers
190
Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
User Avatar
4 votes
2 answers
198
UGC NET CSE | June 2019 | Part 2 | Question: 75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$
How many states are there in a minimum state automata equivalent to regular expression given below?Regular expression is $a^*b(a+b)$$1$$2$$3$$4$
User Avatar
3 votes
3 answers
200
Ace Test Series: Theory Of Computation - Finite Automata
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language?$4$$1...
User Avatar
3 votes
2 answers
201
ACE ACADEMY: TOC
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ? (a) 4 (b) 16 (c) 20 (d) 24
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ?(a) 4 (b) 16 (c) 20 ...
User Avatar
3 votes
1 answer
202
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
User Avatar
Page: