# Recent questions tagged finite-automata

0 votes
0 answers 7 views
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
0 votes
1 answer 11 views
while making compound automata do we have to include the dead states too in the cartesian product ? or can we ignore the dead states and then make the compound automata?
0 votes
0 answers 16 views
What is the NFA that does not accept strings ending “101” ?
5 votes
3 answers 1.2K views
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$
2 votes
2 answers 738 views
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________
2 votes
2 answers 660 views
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}$
0 votes
1 answer 435 views
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?$
1 vote
1 answer 37 views
Can anyone draw the DFA’s for the question mentioned?
0 votes
0 answers 14 views
1) Let ∑ = {D , L}. Find a DFA that accepts Password (P) with the following conditions: - | P | ≥ 4 - P begins with a letter and ends with a letter. - P contains at least one digit. 2) Let ∑ = { 0..9 , : }. Find ... . Consider the following DFA that has access to the laboratories of company controlled. The employee number becomes read as a binary number. Which employee numbers are accepted.
0 votes
1 answer 48 views
Convert the Following DFA to Regular Expression using GNFA.
0 votes
0 answers 15 views
Consider the following regular expression: (a+b) a) Convert the given regular expression to NFA-ε. b) Convert the NFA-ε obtained in a) to NFA.
0 votes
0 answers 50 views
Is my regular expression correct for language which does not have 100 as substring? Inspired from https://gateoverflow.in/2260/gate1997-6-4
0 votes
2 answers 67 views
hi guys, I have a doubt- if two DFA accept the same set of language then are they equal? why or why not? answer really appreciated
0 votes
0 answers 12 views
How to identify when to use DFA cross product,concatenation or union?Pls explain with examples if possible.
0 votes
1 answer 86 views
A traffic signal cycles from RED to YELLOW, YELLOW to GREEN, GREEN to RED. In each cycle RED is turned on for 50 seconds, YELLOW is turned on for 40 seconds and GREEN is turned on for 80 seconds. The traffic signal has to be implemented using a Finite State ... The only input to this FSM is a clock of 10 second period. The minimum number of flip flops required to implement this FSM is _____.
0 votes
2 answers 42 views
How to design a DFA for Σ = {0,1} that accepts the set of strings that contains at least two 0's and at most two 1's.
0 votes
1 answer 38 views
L = { w x (w^r)* ∣ w , x ∈ ( a + b ) * } is it regular language? If so, why? The notation W^r means the reverse string of W.
0 votes
0 answers 40 views
I need help in understanding the reasoning behind finding total number of states when positions of particular input is fixed from left hand side or right hand side. The Gate Overflow website shows the formula that for: nth position from the left side of the string is ... the number of states is 2n I want to understand the logic behind this generalized formula. How did we come to this conclusion?
0 votes
0 answers 44 views
Design a DFA (Deterministic Finite Automata) over the inputs {a,b} for “Even number of a’s and |w| mod 3 = 2.” Basically it means we need ot create dfa such that the strings have even number of a’s and at the same time, length of the string divide with 3 gives a remainder of 2. I know how to do for even number of a’s but how to implement the condition of w mod 3 =2? Help needed
0 votes
0 answers 27 views
Why is it so that solving by converting from FA (state diagram given) to RE gives different solution as compared to ARDENS theorem. What is the RE of the state diagram , given in the question by using ARDENS theorem
1 vote
0 answers 98 views
How many three state DFA can be constructed with a designated initial state that accept empty language over the alphabet {a,b}?
0 votes
0 answers 28 views
How to solve the following problem by state elimination method and arrive at the regular expression $(a + \epsilon) (ab)^* (b + \epsilon)$? Find the regular expression for the language $L$ = set of all the strings over $\sum = {a, b}$ where no $2$ $a$'s and no $2$ $b$'s come together.
0 votes
0 answers 29 views
Minimum number of states for dfa accepting strings over {0,1} such that the k-th bit from the right is 1 is 2^k where 2 is the number of alphabets(link:https://gateoverflow.in/63063/dfa). So according to this result, the number of states for the question in this ... of alphabets and k=2. But according to the link a minimal dfa with only 4 states could be found...then how is the result true?
0 votes
0 answers 10 views
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
0 votes
0 answers 9 views
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false
0 votes
0 answers 23 views
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: $\begin{array}{|c|c|c|c|}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$ ... $\widehat{\delta}(q_2, aba)$ is $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
0 votes
0 answers 8 views
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .
0 votes
0 answers 13 views
Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have? $8$ $14$ $15$ $48$
0 votes
0 answers 8 views
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$? $n-1$ $n$ $n+1$ $2^{n-1}$
0 votes
0 answers 11 views
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains $n$ states $n+1$ states $n+2$ states None of the above
0 votes
0 answers 7 views
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$
0 votes
0 answers 13 views
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
0 votes
0 answers 16 views
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state) $\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & \textbf{a} & \textbf{b} \\\hline \text{$\rightarrow1$} & \text{1} & \text{2} \\\hline \text{$ ...
0 votes
0 answers 8 views
Definition of a language $L$ with alphabet $\{a\}$ is given as following.$L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$What is the minimum number of states needed in a DFA to recognize $L$? $k+1$ $n+1$ $2^{n+1}$ $2^{k+1}$
0 votes
0 answers 10 views
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .
0 votes
0 answers 12 views
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least $N^2$ $2^N$ $2N$ $N!$
0 votes
0 answers 5 views
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
0 votes
0 answers 16 views
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^*$ $0^*1^*1+11^*0^*1$ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
0 votes
0 answers 10 views
Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)? $4$ $5$ $6$ $8$
0 votes
0 answers 9 views
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is $2$ $5$ $8$ $3$