Recent questions tagged finite-automata

if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
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?
What is the NFA that does not accept strings ending “101” ?
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$
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________
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}$
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
Can anyone draw the DFA’s for the question mentioned?
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.
Convert the Following DFA to Regular Expression using GNFA.
Consider the following regular expression: (a+b) a) Convert the given regular expression to NFA-ε. b) Convert the NFA-ε obtained in a) to NFA.
Is my regular expression correct for language which does not have 100 as substring? Inspired from https://gateoverflow.in/2260/gate1997-6-4
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
How to identify when to use DFA cross product,concatenation or union?Pls explain with examples if possible.
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 _____.
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.
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.
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?
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
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
How many three state DFA can be constructed with a designated initial state that accept empty language over the alphabet {a,b}?
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.
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?
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
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
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 \}$
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 ___________ .
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$
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}$
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
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\}$
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 _______
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{$ ...
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}$
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 ______________ .
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!$
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_____________.
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
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$
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$