Register

Recent questions tagged finite-automata

0 votes
0 answers
302
General Query: Self doubt(Math+Automata)
Can somebody explain What is identity permutation?
Can somebody explainWhat is identity permutation?
User Avatar
0 votes
0 answers
305
Peter Linz Edition 4 Exercise 2.4 Question 10 (Page No. 69)
Prove the following: If the states $q_a$ and $q_b$ are indistinguishable, and if $q_a$ and $q_c$ are distinguishable, then $q_b$ and $q_c$ must be distinguishable.
Prove the following: If the states $q_a$ and $q_b$ are indistinguishable, and if $q_a$ and $q_c$ aredistinguishable, then $q_b$ and $q_c$ must be distinguishable.
User Avatar
0 votes
0 answers
308
Peter Linz Edition 4 Exercise 2.4 Question 5 (Page No. 69)
Show that if $L$ is a nonempty language such that any $w$ in $L$ has length at least $n$, then any dfa accepting $L$ must have at least $n + 1$ states.
Show that if $L$ is a nonempty language such that any $w$ in $L$ has length at least $n$, then any dfaaccepting $L$ must have at least $n + 1$ states.
User Avatar
2 votes
0 answers
313
Peter Linz Edition 4 Exercise 2.3 Question 13 (Page No. 62)
Give a simple verbal description of the language accepted by the dfa in following figure. Use this to find another dfa, equivalent to the given one, but with fewer states.
Give a simple verbal description of the language accepted by the dfa in following figure.Use this to find another dfa, equivalent to the given one, but with fewer states....
User Avatar
1 votes
1 answer
317
Peter Linz Edition 4 Exercise 2.3 Question 9 (Page No. 62)
Let $L$ be a regular language that does not contain $λ$. Show that there exists an nfa without $λ$- transitions and with a single final state that accepts $L$.
Let $L$ be a regular language that does not contain $λ$. Show that there exists an nfa without $λ$-transitions and with a single final state that accepts $L$.
User Avatar
0 votes
1 answer
319
Peter Linz Edition 4 Exercise 2.3 Question 7 (Page No. 62)
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we make a similar claim for dfa’s?
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with onlyone final state. Can we make a similar claim for dfa’s?
User Avatar
2 votes
1 answer
325
Virtual Gate Test Series: Theory Of Computation - Finite Automata
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything? answer is 20 or 64?
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?answer is 20 o...
User Avatar
Page: