The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exam Category
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Search results for theoryofcomputation
+8
votes
1
answer
1
How to construct an automata with even number of a's and odd number of b's?
asked
Mar 14, 2016
in
Theory of Computation
by
Gourab_Classic
(
61
points)

11.3k
views
minimalstateautomata
theoryofcomputation
finiteautomata
permutationsandcombinations
+29
votes
4
answers
2
GATE2016244
Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$, $L_{2} = \left\{\left\langle M \right\rangle \mid M \text { takes at least 2016 steps on all inputs} \right\}$ and $L_{ ... L_{3}$ are not recursive $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive
asked
Feb 12, 2016
in
Theory of Computation
by
Akash Kanase
Veteran
(
46.8k
points)

4.2k
views
gate20162
theoryofcomputation
turingmachine
+8
votes
11
answers
3
GATE2017122
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 finitestate automaton (DFA) accepting $L$ is ___________ .
asked
Feb 14
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

2.4k
views
gate20171
theoryofcomputation
finiteautomata
numericalanswers
+14
votes
6
answers
4
GATE2017110
Consider the following contextfree grammar over the alphabet $\sum$ = {$a,b,c$} with $S$ as the start symbol: $S$ $\rightarrow$ $abScT$  $abcT$ $T$ $\rightarrow$ $bT$  $b$ Which one of the following represents the language generated by the above grammar? (A) {$\left ( ab \right )^{n}\left ( cb ... geq$ 1 } (D) {$\left ( ab \right )^{n}\left ( cb^{n} \right )^{m}$  $m,n$ $\geq$ 1 }
asked
Feb 14
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

1.9k
views
gate20171
theoryofcomputation
contextfreelanguage
normal
+5
votes
4
answers
5
set of strings with atmost one pair of consecutive 0's and at most one pair of consecutive 1's
asked
Jun 24, 2016
in
Theory of Computation
by
Sankaranarayanan P.N
Veteran
(
11.7k
points)

3.7k
views
theoryofcomputation
regularexpressions
+15
votes
2
answers
6
GATE2017139
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$, ... is computable then $L_{f}$ is recursive, but not conversely. (D) If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
asked
Feb 14
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

1.8k
views
gate20171
theoryofcomputation
decidability
difficult
+19
votes
6
answers
7
GATE200634
Consider the regular language $L=(111+11111)^{*}$ . The minimum number of states in any DFA accepting this languages is: 3 5 8 9
asked
Sep 22, 2014
in
Theory of Computation
by
Rucha Shelke
Loyal
(
4.3k
points)

3.2k
views
gate2006
theoryofcomputation
finiteautomata
normal
+32
votes
3
answers
8
GATE2014235
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$. Let $$L=\left\{\langle M \rangle \mid M \text{ is a Turing machine}\\\text{ that accepts a ... \right\}.$$ Then $L$ is decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable
asked
Sep 28, 2014
in
Theory of Computation
by
jothee
Veteran
(
96.5k
points)

3.1k
views
gate20142
theoryofcomputation
turingmachine
normal
+1
vote
0
answers
9
Intro to Formal Languages and Automata Peter Linz Ex. #2.1.2e
asked
Sep 8
in
Theory of Computation
by
Garrett McClure
Junior
(
585
points)

1.8k
views
theoryofcomputation
peterlinz
grammar
dfa
regularlanguages
+6
votes
6
answers
10
GATE2017204
Let $L_1, L_2$ be any two contextfree languages and $R$ be any regular language. Then which of the following is/are CORRECT? $L_1 \cup L_2$ is contextfree $\overline{L_1}$ is contextfree $L_1  R$ is contextfree $L_1 \cap L_2$ is contextfree I, II and IV only I and III only II and IV only I only
asked
Feb 14
in
Theory of Computation
by
khushtak
Boss
(
7.9k
points)

1.3k
views
gate20172
theoryofcomputation
closureproperty
+22
votes
3
answers
11
GATE2015151
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}, \perp, F =\left \{ q_{2} \right ... The state transition is as 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
asked
Feb 13, 2015
in
Theory of Computation
by
makhdoom ghaya
Veteran
(
42.4k
points)

2.9k
views
gate20151
theoryofcomputation
pushdownautomata
normal
+20
votes
3
answers
12
GATE200354
Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a triplet, whose ... , but $L'$ is not $L'$ is recursively enumerable, but $ L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable
asked
Sep 8, 2014
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

3k
views
theoryofcomputation
turingmachine
gate2003
difficult
+8
votes
3
answers
13
GATE2017241
Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted by a Turing machine $M$. Which of the following decision problems are undecidable? Given a regular expression $R$ and ... string $w$, is $w \in L(M)$? I and IV only II and III only II, III and IV only III and IV only
asked
Feb 14
in
Theory of Computation
by
Madhav
Active
(
2k
points)

1.2k
views
gate20172
theoryofcomputation
decidability
+6
votes
3
answers
14
GATE2017138
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}m,n \geq 0 \right \}$. Which of the following are contextfree languages? I. $L_{1} \cup L_{2}$ II. $L_{1} \cap L_{2}$ (A) I only (B) II only (C) I and II (D) Neither I nor II
asked
Feb 14
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

1.3k
views
gate20171
theoryofcomputation
contextfreelanguage
normal
+6
votes
8
answers
15
GATE2017216
Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$
asked
Feb 14
in
Theory of Computation
by
khushtak
Boss
(
7.9k
points)

983
views
gate20172
theoryofcomputation
contextfreelanguage
+15
votes
7
answers
16
GATE2016142
Consider the following contextfree grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generaed by $G_1$ and $G_2$ ,respectively? $\{ a^mb^n \mid m > 0 \ ... $\{ a^mb^n \mid m \geq 0 \ and \ n >0\} \ and \ \{ a^mb^n \mid m > 0 \ or \ n>0\}$
asked
Feb 12, 2016
in
Theory of Computation
by
Sandeep Singh
Boss
(
9.2k
points)

2.1k
views
gate20161
theoryofcomputation
contextfreelanguage
normal
+6
votes
8
answers
17
GATE2017137
Consider the contextfree grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are nonterminals. $G_{1}:S\rightarrow aSbT, T\rightarrow cT\in$ $G_{2}:S\rightarrow bSaT, T\rightarrow cT\in$ The language $L\left ( G_{1} \right )\cap L(G_{2})$ is (A) Finite. (B) Not finite but regular. (C) ContextFree but not regular. (D) Recursive but not contextfree.
asked
Feb 14
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

1.2k
views
gate20171
theoryofcomputation
contextfreelanguage
identifyclasslanguage
normal
+7
votes
3
answers
18
ACE GATE test series 2018
Consider the following contextfree grammar S → SS +  SS* a It is a)LL(1) b)LR(0) c)Both d)none
asked
Sep 6
in
Compiler Design
by
smelly indian
(
245
points)

204
views
gate2018
theoryofcomputation
acetestseries
compilerdesign
parsing
lrparser
ll1parser
+5
votes
6
answers
19
GATE2017134
If $G$ is a grammar with productions $S\rightarrow SaSaSbbSaSS\in$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? (A) $abab$ (B) $aaab$ (C) $abbaa$ (D) $babba$
asked
Feb 14
in
Theory of Computation
by
Arjun
Veteran
(
326k
points)

857
views
gate20171
theoryofcomputation
contextfreelanguage
normal
+5
votes
1
answer
20
DCFL or NOT
Consider the follwoing Language L1= {0n1*0n  n>0} is DCFL or Not? L2= {0n1+0n  n>0} is DCFL or Not?
asked
Nov 4
in
Theory of Computation
by
Anu007
Loyal
(
4.9k
points)

120
views
theoryofcomputation
dcfl
Page:
1
2
3
...
next »
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
Recent Posts
Jobs @cvppindia
How to be productive?For all Members,GATE Aspirants, everybody associated with "GO Family"
How to Do preparation for Gate2018
How to write nice answers/questions in GO
Organizing NET Questions
Follow @csegate
Gatecse
Search results for theoryofcomputation
Recent Blog Comments
Visit exam center at your own risk ...
@papesh, Thanks. Helpful Post. Waiting for the ...
Thank you very much. :)
written exam wil held in jammu only..:(
that can be only obtained by self motivation and ...
28,946
questions
36,791
answers
91,045
comments
34,687
users