search
Log In

Recent questions tagged finite-automata

6 votes
3 answers
1
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states? $L-\{01\}$ $L \cup \{01\}$ $\{0,1\}^* – L$ $L \cdot L$
asked Feb 18 in Theory of Computation Arjun 1.4k views
3 votes
3 answers
2
3 votes
2 answers
3
Suppose we want to design a synchronous circuit that processes a string of $0$'s and $1$'s. Given a string, it produces another string by replacing the first $1$ in any subsequence of consecutive $1$'s by a $0$ ... $\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}$
asked Feb 18 in Theory of Computation Arjun 711 views
0 votes
1 answer
4
Consider the following language: $L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$ Which one of the following deterministic finite automata accepts $L?$
asked Feb 18 in Theory of Computation Arjun 490 views
0 votes
1 answer
5
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
asked Apr 2, 2020 in Theory of Computation Lakshman Patel RJIT 274 views
1 vote
4 answers
6
1 vote
3 answers
7
3 votes
3 answers
13
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, 2020 in Theory of Computation Lakshman Patel RJIT 4k views
0 votes
2 answers
14
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, 2020 in Theory of Computation Lakshman Patel RJIT 358 views
2 votes
1 answer
15
0 votes
1 answer
16
0 votes
6 answers
17
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, 2020 in Theory of Computation Lakshman Patel RJIT 2.7k views
5 votes
5 answers
18
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
asked Jan 13, 2020 in Theory of Computation Satbir 3k views
1 vote
0 answers
19
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 213 views
0 votes
0 answers
20
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 129 views
0 votes
0 answers
21
0 votes
1 answer
22
...