Recent questions tagged finite-automata

1
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
1 vote
2
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$ $DFA$ $NFA - 1$ All of the options
3
Complement of a $DFA$ can be obtained by : making starting state as final state. make final as a starting state. making final states non-final and non-final as final. None of the options
4
Concatenation Operation refers to which of the following set operations : Union Dot Kleene None of the options
5
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$
6
What is the relation between $DFA$ and $NFA$ on the basis of computational power ? $DFA$ > $NFA$ $NFA$ > $DFA$ Equal Can't be said
1 vote
7
How many DFA's exits with two states over input alphabet $\left \{ 0,1 \right \}$ $16$ $26$ $32$ $64$
8
Finite automata requires minimum ____________ number of stacks. $1$ $0$ $2$ None of the options
9
Palindromes can't be recognized by any Finite State Automata because: FSA cannot remember arbitrarily large amount of information. FSA cannot deterministically fix the midpoint. Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half. All of the above.
10
Given two DFA's $M1$ and $M2$. They are equivalent if $M1$ and $M2$ has the same number of states $M1$ and $M2$ accepts the same language i.e $L(M1)=L(M2)$ $M1$ and $M2$ has the same number of final states None of the above
11
$(00+01+10)(0+1)^*$ represents Strings not starting with $11$ Strings of odd length Strings starting with $00$ Strings of even length
12
What is the complement of the language accepted by the NFA shown below? $\not{O}$ $\{\epsilon\}$ $a^*$ $\{a,\epsilon\}$ $1$ $2$ $3$ $4$
13
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
14
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
1 vote
15
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$. The squares along the boundary of the rectangle contain the symbol $\#$ and the internal squares contain ... . Consider the problem of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
16
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a $2DFA$ is finite and is just large ... $E_{2DFA}$ is not decidable.
17
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.)
18
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.)
19
Let $BAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some string containing an equal number of 0s and 1s}\}$. Show that $BAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
20
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true? The shortest word in $L(A)$ has length at most $n-1.$ The shortest word in $L(A)$ has length at least $n.$ The shortest word not in $L(A)$ has length at most $n-1.$ The shortest word not in $L(A)$ has length at least $n.$