search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.

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??
asked Jun 8 in Theory of Computation promise 5 points 7 views
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?
asked May 16 in Theory of Computation rythmrana 5 points 11 views
0 votes
0 answers 16 views
What is the NFA that does not accept strings ending “101” ?
asked Apr 7 in Theory of Computation shri385 5 points 16 views
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$
asked Feb 18 in Theory of Computation Arjun 257 points 1.2K views
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 ___________
asked Feb 18 in Theory of Computation Arjun 257 points 738 views
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}$
asked Feb 18 in Theory of Computation Arjun 257 points 660 views
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?$
asked Feb 18 in Theory of Computation Arjun 257 points 435 views
1 vote
1 answer 37 views
Can anyone draw the DFA’s for the question mentioned?
asked Jan 22 in Theory of Computation phaneendrababu 11 points 37 views
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.
asked Dec 29, 2020 in Theory of Computation MotasemMobayyed 5 points 14 views
0 votes
1 answer 48 views
Convert the Following DFA to Regular Expression using GNFA.
asked Dec 26, 2020 in Theory of Computation M.hamza 5 points 48 views
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.
asked Dec 16, 2020 in Others Ehtisham 5 points 15 views
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
asked Dec 9, 2020 in Theory of Computation ijnuhb 747 points 50 views
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
asked Oct 24, 2020 in Theory of Computation rish1602 9 points 67 views
0 votes
0 answers 12 views
How to identify when to use DFA cross product,concatenation or union?Pls explain with examples if possible.
asked Oct 2, 2020 in Theory of Computation the_dalela 5 points 12 views
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 _____.
asked Aug 29, 2020 in Digital Logic Animesh Sinha 25 points 86 views
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.
asked Aug 25, 2020 in Compiler Design abhish1mishra 5 points 42 views
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.
asked Aug 18, 2020 in Theory of Computation abhijeet at 9 points 38 views
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?
asked Aug 1, 2020 in Theory of Computation aryashah2k 2 points 40 views
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
asked Jul 24, 2020 in Theory of Computation aryashah2k 2 points 44 views
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
asked Jul 18, 2020 in Theory of Computation prajjwalsingh_11 15 points 27 views
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}?
asked May 16, 2020 in Theory of Computation Shreya2002 9 points 98 views
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.
asked Apr 24, 2020 in Theory of Computation intgate 9 points 28 views
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?
asked Apr 22, 2020 in Theory of Computation Deterministic 31 points 29 views
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$
asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views
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
asked Apr 18, 2020 in Theory of Computation admin 573 points 9 views
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 \}$
asked Apr 18, 2020 in Theory of Computation admin 573 points 23 views
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 ___________ .
asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views
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$
asked Apr 18, 2020 in Theory of Computation admin 573 points 13 views
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}$
asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views
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
asked Apr 18, 2020 in Theory of Computation admin 573 points 11 views
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\}$
asked Apr 18, 2020 in Theory of Computation admin 573 points 7 views
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 _______
asked Apr 18, 2020 in Theory of Computation admin 573 points 13 views
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{$\rightarrow$ $1$} & \text{1} & \text{2} \\\hline \text{$ ...
asked Apr 18, 2020 in Theory of Computation admin 573 points 16 views
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}$
asked Apr 18, 2020 in Theory of Computation admin 573 points 8 views
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 ______________ .
asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views
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!$
asked Apr 18, 2020 in Theory of Computation admin 573 points 12 views
0 votes
0 answers 5 views
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
asked Apr 18, 2020 in Theory of Computation admin 573 points 16 views
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$
asked Apr 18, 2020 in Theory of Computation admin 573 points 10 views
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$
asked Apr 18, 2020 in Theory of Computation admin 573 points 9 views
...