search
Log In

Recent questions tagged finite-automata

0 votes
3 answers
2
1 vote
2 answers
8
Regarding power of recognition of language, which of the following statements is false? Non deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic push-down automata are equivalent to deterministic push-down ... are equivalent to deterministic push-down automata. Multi-tape Turing Machines are equivalent to Single-tape Turing Machines.
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 263 views
3 votes
3 answers
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.
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 799 views
0 votes
2 answers
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
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 185 views
2 votes
1 answer
11
0 votes
1 answer
12
0 votes
6 answers
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.
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 1.1k views
4 votes
6 answers
14
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
asked Jan 13 in Theory of Computation Satbir 1.3k views
1 vote
0 answers
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 141 views
0 votes
0 answers
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 70 views
0 votes
0 answers
17
0 votes
1 answer
18
0 votes
0 answers
19
0 votes
1 answer
24
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.$
asked Sep 13, 2019 in Theory of Computation gatecse 186 views
1 vote
1 answer
25
Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
asked Sep 13, 2019 in Theory of Computation gatecse 162 views
3 votes
3 answers
26
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$
asked Jul 2, 2019 in Theory of Computation Arjun 1.3k views
...