Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Year
Exams
Recent questions tagged theoryofcomputation
0
votes
1
answer
Context Free Language
Is this CFL? L = {wcwr  w, c ϵ {0,1}+ and c = 2}
asked
14 hours
ago
in
Theory of Computation
by
sameer2009
(
6
points)

9
views
theoryofcomputation
contextfreelanguages
0
votes
0
answers
Show that the language L = w1cw2 : w1, w2 ∈ {a, b}+ , {w1 ≠ w^R2 } with Σ = {a, b, c}, is contextfree.
asked
5 days
ago
in
Theory of Computation
by
roh
(
17
points)

10
views
theoryofcomputation
#gatebook
#toc
#peterlinz
0
votes
0
answers
Peter Linz Exercise8.2 Context Free Lnaguages
Show that the following language is context free L={$w\epsilon (a, b)$* : $n_{a}(w)=n_{b}(w)$, w does not contain the substring aab}
asked
Jun 16
in
Theory of Computation
by
aditi19
(
57
points)

8
views
theoryofcomputation
peterlinz
contextfreelanguages
#toc
0
votes
1
answer
Made easy Theory book
Is $a ^{n} b^{2n} c^{ 3n}$ such that $n >0$ context free or not ? full explanation please.
asked
Jun 15
in
Theory of Computation
by
Tajbar Singh negi
(
9
points)

15
views
theoryofcomputation
0
votes
0
answers
Regular Expression
what is the regular expression for strings of length atmost 2 over {a,b}. Plz give detailed soln.
asked
Jun 11
in
Theory of Computation
by
Vaishalikashyap
(
10
points)

18
views
theoryofcomputation
0
votes
0
answers
Peter Linz Theory of Computation Exercise 5.1 Question15
asked
Jun 11
in
Theory of Computation
by
aditi19
(
57
points)

10
views
theoryofcomputation
peterlinz
#toc
contextfreelanguages
0
votes
0
answers
TOC GATE201332 doubt regarding dcfl
$L2 = \left \{ 0^p1^q0^r ∣ p,q,r ≥ 0, p ≠ r \right \}$ Is the above language dcfl? The comments in the question state that it is but what about the case when #1’s = 0. Then how is the first half of 0’s separated from the second half of 0’s deterministically? Ref – https://gateoverflow.in/1543/gate201332
asked
May 30
in
Theory of Computation
by
abhijit_m
(
6
points)

13
views
usergate2013
usermod
theoryofcomputation
identifyclasslanguage
dcfl
0
votes
1
answer
TIFR2020B2
Consider the following statements . 1. The intersection of two context  free languages is always context  free . 2. The super  set of a context  free language is never regular. 3. The subset of a decidable language is always decidable . 4. Let $\sum$ = { a , b , c } . Let L$\subseteq$ ... ) and ( 3 ) ( d ) Only ( 4 ) ( e ) None of ( 1 ) , ( 2 ) , ( 3 ) , ( 4 ) are true
asked
May 26
in
Theory of Computation
by
prnv28
(
6
points)

11
views
tifr2020
theoryofcomputation
+1
vote
0
answers
Theory of computation No of state in dfa
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
in
Theory of Computation
by
Shreya2002
(
7
points)

45
views
#toc
theoryofcomputation
#testseries
#dfa
0
votes
0
answers
Self Doubt Turing Machine
Write the implementation level Turing Machine for following language: L={w∈ {a,b}*, w: 2na(w) nb(w) 3na(w)}
asked
May 3
in
Theory of Computation
by
jainpawan21
(
8
points)

5
views
turingmachine
#toc
theoryofcomputation
0
votes
0
answers
How to construct a deterministic finite automation equivalent to the grammar S>aSbSaA, A>bB, B>aC
asked
May 1
in
Theory of Computation
by
Sarika lozy
(
6
points)

12
views
theoryofcomputation
#toc
#theoryofcomputerscience
0
votes
0
answers
SELF DOUBT(TOCWhat type of language is this.)
if we have a language like: L={3,9,27,81,273….} what is this ? is this regular,CFL,CSL or recursive or recursively enumerable?
asked
Apr 29
in
Theory of Computation
by
Doraemon
(
115
points)

7
views
theoryofcomputation
0
votes
0
answers
TOC The R.E L(r) = (a+ b*) U ε. Is the grammar with productions generated over nonterminals {S, A} ambiguous?
asked
Apr 27
in
Theory of Computation
by
siddharths067
(
7
points)

9
views
theoryofcomputation
#toc
0
votes
0
answers
Regular Expression/Language
Set of possible strings generated by Regular expression (11+111)* should contain {null, {11}, {111}, {11111},…}. Can this set contain the strings which are generated considering the part of the above RE partially, i.e., will {1111} (length 4), generated by considering either {11} partially or {111} partially. Can such string be a part of the language ?
asked
Apr 25
in
Theory of Computation
by
hridayN
(
6
points)

19
views
theoryofcomputation
regularlanguages
#regularlanguage
0
votes
0
answers
self doubt on dfa
Minimum number of states for dfa accepting strings over {0,1} such that the kth 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 ... 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
in
Theory of Computation
by
Deterministic
(
13
points)

20
views
theoryofcomputation
#dfa
0
votes
0
answers
Number of states in dfa for 2nd last bit is a
There are 4 states in the dfa of 2nd last bit is a. Generally we do 2^n where nth last bit is given. I am unable to visualise this how this formula works and why?
asked
Apr 21
in
Theory of Computation
by
darshansharma_
(
13
points)

22
views
theoryofcomputation
0
votes
0
answers
Why we need to remove null production from grammar?
asked
Apr 19
in
Theory of Computation
by
darshansharma_
(
13
points)

9
views
theoryofcomputation
compilerdesign
0
votes
0
answers
Write the grammar for equal number of a and b?
Write all the possible grammar for the language => number of a = number of b Please explain the reason why the grammar is valid?
asked
Apr 19
in
Theory of Computation
by
darshansharma_
(
13
points)

2
views
theoryofcomputation
0
votes
0
answers
GATE2016244 Video Solution
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\}$ ... are not recursive $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate20162
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE2014235 Video Solution
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$ ... $L$ is: decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate20142
theoryofcomputation
turingmachine
normal
videosolution
0
votes
0
answers
GATE2014236 Video Solution
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ ... following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

4
views
gate20142
theoryofcomputation
normal
regularlanguages
videosolution
0
votes
0
answers
GATE2015151 Video Solution
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$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

4
views
gate20151
theoryofcomputation
pushdownautomata
normal
videosolution
0
votes
0
answers
GATE200354 Video Solution
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 ... $L'$ is recursively enumerable, but $ L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
theoryofcomputation
turingmachine
gate2003
difficult
videosolution
0
votes
0
answers
GATE200634 Video Solution
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 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate2006
theoryofcomputation
finiteautomata
normal
minimalstateautomata
videosolution
0
votes
0
answers
GATE2016242 Video Solution
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 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate20162
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE201915 Video Solution
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

8
views
gate2019
theoryofcomputation
pumpinglemma
videosolution
0
votes
0
answers
GATE2004IT40 Video Solution
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$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate2004it
theoryofcomputation
pushdownautomata
normal
videosolution
0
votes
0
answers
GATE19976.4 Video Solution
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring? $0^*(1+0)^*$ $0^*1010^*$ $0^*1^*01^*$ $0^*(10+1)^*$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate1997
theoryofcomputation
regularexpressions
normal
videosolution
0
votes
0
answers
GATE2017239 Video Solution
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}{cccc}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

9
views
gate20172
theoryofcomputation
finiteautomata
videosolution
0
votes
0
answers
GATE2017139 Video Solution
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 ... $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

3
views
gate20171
theoryofcomputation
decidability
difficult
videosolution
0
votes
0
answers
GATE201852 Video Solution
Given a language $L$, define $L^i$ as follows:$L^0 = \{ \varepsilon \}$$L^i = L^{i1} \bullet L \text{ for all } I >0$The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate2018
theoryofcomputation
numericalanswers
regularlanguages
videosolution
0
votes
0
answers
GATE2017122 Video Solution
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
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate20171
theoryofcomputation
finiteautomata
numericalanswers
minimalstateautomata
videosolution
0
votes
0
answers
GATE200629 Video Solution
If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$'s in $s$ and $n_1(s)$ the number of $1$'s in $s$. Which one of the following languages is not regular? $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3digit prime } \right \}$ ... $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate2006
theoryofcomputation
normal
regularlanguages
videosolution
0
votes
0
answers
GATE2016143 Video Solution
Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma = \{X,Z\}$. $Z$ is the initial stack symbol. Let $L$ ... on every input $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic contextfree
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

8
views
gate20161
theoryofcomputation
pushdownautomata
normal
videosolution
0
votes
0
answers
GATE20012.5 Video Solution
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 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate2001
theoryofcomputation
finiteautomata
minimalstateautomata
videosolution
0
votes
0
answers
GATE201835 Video Solution
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are contextfree? I and IV only I and II only II and III only II and IV only
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate2018
theoryofcomputation
identifyclasslanguage
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2016142 Video Solution
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 generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate20161
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE200315 Video Solution
If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true? $L$ is necessarily finite $L$ is regular but not necessarily finite $L$ is context free but not necessarily regular $L$ is recursive but not necessarily contextfree
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
theoryofcomputation
gate2003
normal
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE2017110 Video Solution
Consider the following contextfree grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

1
view
gate20171
theoryofcomputation
contextfreelanguages
normal
videosolution
0
votes
0
answers
GATE2016118 Video Solution
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s? $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$ $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$ $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$ $00(0+1)^*11 +11(0+1)^*00$
asked
Apr 19
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate20161
theoryofcomputation
regularexpressions
normal
videosolution
Page:
1
2
3
4
...
12
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Jul 2020
bittujash
6 Points
RavGopal
4 Points
ankeshsingh
2 Points
prakhar123
1 Points
arpit_18
1 Points
pravincesingh
1 Points
Shaik Masthan
1 Points
srestha
1 Points
sameer2009
1 Points
7,525
questions
1,776
answers
10,835
comments
90,464
users