Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for automata
19
votes
3
answers
1
How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA
The alphabets are a and b.Construct a DFA
Gourab_Classic
109k
views
Gourab_Classic
asked
Mar 14, 2016
Theory of Computation
minimal-state-automata
theory-of-computation
finite-automata
combinatory
+
–
5
votes
4
answers
2
Difference between DPDA and NPDA?
Amit Sharma
39.0k
views
Amit Sharma
asked
Jun 1, 2016
Theory of Computation
theory-of-computation
pushdown-automata
+
–
77
votes
12
answers
3
GATE CSE 2017 Set 2 | Question: 39
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...
Arjun
28.4k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set2
theory-of-computation
finite-automata
+
–
54
votes
15
answers
4
GATE CSE 2017 Set 1 | Question: 22
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 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-...
Arjun
29.3k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set1
theory-of-computation
finite-automata
numerical-answers
minimal-state-automata
+
–
93
votes
8
answers
5
GATE CSE 2006 | Question: 34
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 regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$
Rucha Shelke
34.4k
views
Rucha Shelke
asked
Sep 22, 2014
Theory of Computation
gatecse-2006
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
83
votes
4
answers
6
GATE CSE 2015 Set 1 | Question: 51
Consider the NPDA ... follows: Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton? $10110$ $10010$ $01010$ $01001$
Consider the NPDA $$ \left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \p...
makhdoom ghaya
23.8k
views
makhdoom ghaya
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
pushdown-automata
normal
+
–
71
votes
14
answers
7
GATE CSE 2012 | Question: 12
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\}$
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...
gatecse
19.4k
views
gatecse
asked
Aug 5, 2014
Theory of Computation
gatecse-2012
finite-automata
easy
theory-of-computation
+
–
55
votes
9
answers
8
GATE IT 2004 | Question: 40
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where $K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and $Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$. Which one of the following strings is not a member of $L(M)$? $aaa$ $aabab$ $baaba$ $bab$
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where$K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and$Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsil...
Ishrat Jahan
42.6k
views
Ishrat Jahan
asked
Nov 2, 2014
Theory of Computation
gateit-2004
theory-of-computation
pushdown-automata
normal
+
–
57
votes
5
answers
9
GATE CSE 2019 | Question: 48
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$ ... Consider the language $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
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$...
Arjun
20.3k
views
Arjun
asked
Feb 7, 2019
Theory of Computation
gatecse-2019
numerical-answers
theory-of-computation
finite-automata
minimal-state-automata
difficult
2-marks
+
–
62
votes
9
answers
10
GATE CSE 2010 | Question: 41
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}$
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 automati...
go_editor
24.0k
views
go_editor
asked
Sep 30, 2014
Theory of Computation
gatecse-2010
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
31
votes
4
answers
11
GATE CSE 2022 | Question: 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below? $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$ $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$ $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$ $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$
Which one of the following regular expressions correctly represents the language of the finite automaton given below?$ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$$(ab^{\ast...
Arjun
17.8k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
finite-automata
regular-expression
1-mark
+
–
32
votes
3
answers
12
GATE IT 2006 | Question: 31
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA? $\{a^nb^nc^n \mid n ≥ 0\}$ $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$ $\{a^nb^n \mid n ≥ 0\}$ $\{a^mb^n \mid m, n ≥ 0\}$
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?$\{a^nb^nc^n \mid n ≥ 0\}$$\{a^lb^mc^n \mid ...
Ishrat Jahan
18.1k
views
Ishrat Jahan
asked
Oct 31, 2014
Theory of Computation
gateit-2006
theory-of-computation
pushdown-automata
normal
+
–
39
votes
4
answers
13
GATE CSE 1998 | Question: 2.5
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$
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$...
Kathleen
17.4k
views
Kathleen
asked
Sep 25, 2014
Theory of Computation
gate1998
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
79
votes
3
answers
14
GATE CSE 2016 Set 2 | Question: 42
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
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 languag...
Akash Kanase
25.6k
views
Akash Kanase
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set2
theory-of-computation
finite-automata
normal
+
–
56
votes
4
answers
15
GATE CSE 1998 | Question: 1.10
Which of the following set can be recognized by a Deterministic Finite state Automaton? The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary The numbers $1, 2, 4, 8,\dots 2^n, \dots$ written in unary The set of binary string in which the number of zeros is the same as the number of ones. The set $\{1, 101, 11011, 1110111, \dots\}$
Which of the following set can be recognized by a Deterministic Finite state Automaton?The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binaryThe numbers $1, 2, 4, 8...
Kathleen
15.6k
views
Kathleen
asked
Sep 25, 2014
Theory of Computation
gate1998
theory-of-computation
finite-automata
normal
+
–
61
votes
7
answers
16
GATE CSE 2003 | Question: 50
Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is $1$ $5$ $7$ $8$
Consider the following deterministic finite state automaton $M$.Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $...
Kathleen
15.0k
views
Kathleen
asked
Sep 17, 2014
Theory of Computation
gatecse-2003
theory-of-computation
finite-automata
normal
+
–
12
votes
5
answers
17
GATE CSE 2023 | Question: 30
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ ... $\left.0 \leq n\right\}$ $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}...
admin
7.1k
views
admin
asked
Feb 15, 2023
Theory of Computation
gatecse-2023
theory-of-computation
pushdown-automata
2-marks
+
–
56
votes
6
answers
18
GATE IT 2008 | Question: 36
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$. $M_1$ $M_2$ Which one of the following is TRUE? $L_1 = L_2$ $L_1 \subset L_2$ $L_1 \cap L_{2}^{C} = \varnothing $ $L_1 \cup L_2 \neq L_1$
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.$M_1$$M_2$ Which one of the following is TRUE?$L_1 = L_2$$L_1 \subset L_2$$L_1 \ca...
Ishrat Jahan
12.6k
views
Ishrat Jahan
asked
Oct 28, 2014
Theory of Computation
gateit-2008
theory-of-computation
finite-automata
normal
+
–
65
votes
12
answers
19
GATE CSE 2015 Set 1 | Question: 52
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_____________.
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_____________.
makhdoom ghaya
17.3k
views
makhdoom ghaya
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
finite-automata
easy
numerical-answers
minimal-state-automata
+
–
46
votes
7
answers
20
GATE CSE 2009 | Question: 41
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.
Kathleen
21.2k
views
Kathleen
asked
Sep 22, 2014
Theory of Computation
gatecse-2009
theory-of-computation
finite-automata
easy
+
–
Page:
1
2
3
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register