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
Blogs
Previous Year
Exams
Recent questions tagged theoryofcomputation
+1
vote
1
answer
DPDA self doubt. Please explain.
From Wiki. M here is PDA. Please explain both these points. Can someone explain what being said about epsilon transitions? Please explain point 3. How to check conflict between epsilon transition.
asked
Sep 6
in
Theory of Computation
by
iarnav
(
231
points)

36
views
selfdoubt
theoryofcomputation
0
votes
0
answers
Ace test series
asked
Sep 5
in
Theory of Computation
by
ck
(
5
points)

23
views
aceacademytestseries
theoryofcomputation
0
votes
2
answers
Testing whether a language is regular or not.
L =. a^i b^2j  i,j>=1 is regular or not ?
asked
Sep 4
in
Theory of Computation
by
Rsharma29
(
7
points)

64
views
theoryofcomputation
regularlanguage
regulargrammar
regularlanguages
+1
vote
1
answer
Made Easy Topic Wise Test Series
The question says whether the following language is CFL or not(I replaced $ with &): B = {x&w  w is a substring of x, x$\in$\Sigma ^{*}$, &$\in \Sigma$} As per my understanding, w is a substring of x, and x$\in$\Sigma ^{ ... } = {$\Sigma ^{+}$} which is regular, and therefore CFL But in the answer it was given that it is not CFL, Please someone explain.
asked
Sep 4
in
Theory of Computation
by
Ollie
(
453
points)

116
views
madeeasytestseries
theoryofcomputation
0
votes
2
answers
Self Doubt  TOC
What is the difference between reversal and complement of a DFA$?$
asked
Sep 4
in
Theory of Computation
by
Kavya sharma
(
11
points)

58
views
theoryofcomputation
0
votes
1
answer
Self doubt on closure properties
Does complement of non deterministic CFL can be DCFL? please explain.
asked
Sep 4
in
Theory of Computation
by
Akshay sinha
(
9
points)

23
views
theoryofcomputation
closureproperties
complement
+1
vote
1
answer
Decidability: ME
A student want to prove a relation between the “hello” and “world”, where “hello” and “world” are two problems , if the student proves that “hello” is reducible to “world” and “world” is decidable then “hello” is decidable. L={<M>  M is turing machine and $L\left ( M \right )\preceq _{p}\left \{ 0^{p} 1^{2p} p>0 \right \}$} Which one ofthe following is decidable?
asked
Sep 3
in
Theory of Computation
by
srestha
(
1k
points)

67
views
theoryofcomputation
+1
vote
2
answers
#toc #self_doubts #cfl
$L={\;\{\;a^{(m+n)}b^{(m+k)}c^{(k+n)}}, m,n,k ≥ 0 \;\}$ $L$ is CFL or DCFL? My logic is push all $a’s$ and then pop $m$ $b’s$ and push $k$ $b’s$, so here we need non determinism, so it should be CFL and not DCFL. Can anyone design a DPDA for it?
asked
Sep 2
in
Theory of Computation
by
suvradip das
(
113
points)

304
views
theoryofcomputation
selfdoubt
pushdownautomata
contextfreelanguages
0
votes
1
answer
Self Doubt on TOC
If L is not CFL, it doesnot satisfy pumping lemma it is false statement But why? If someone give example for it.
asked
Sep 2
in
Theory of Computation
by
srestha
(
1k
points)

20
views
theoryofcomputation
0
votes
1
answer
Self Doubt: TOC: ACE
Which of the following is recursive language? A)L={<M> M is a DFA and L(M) regular language} B)L={<M> M is a PDA and L(M) regular language} Can I say, CFL is regular or not is undecidable, So, B) will be nonrecursive.
asked
Sep 2
in
Theory of Computation
by
srestha
(
1k
points)

38
views
theoryofcomputation
0
votes
1
answer
#Self_Doubt#TOC
L={aⁿbⁱ n<=i<=2n} Is L CFL?
asked
Aug 31
in
Theory of Computation
by
suvradip das
(
113
points)

53
views
selfdoubt
theoryofcomputation
0
votes
2
answers
Unacdemy Questions
Consider the following language $L =$ w $ x  x is prefix of w, where $w,x\in \left \{ a,b \right \}^{+}$ Which of the following is TRUE? A)L is CFL but not DCFL B)L is CSL but not context free C)L is DCFL but not regular D)None Of these
asked
Aug 27
in
Theory of Computation
by
Ehraz Hasan
(
366
points)

128
views
theoryofcomputation
0
votes
2
answers
Finite Automata
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
in
Compiler Design
by
abhish1mishra
(
5
points)

35
views
theoryofcomputation
finiteautomata
theoryofcomputation
0
votes
2
answers
TOC infinite strings self doubt
When can we say that the string of infinite length is there? Or do we even have string of infinite length at all?
asked
Aug 24
in
Theory of Computation
by
jatinsharma437
(
7
points)

31
views
theoryofcomputation
+1
vote
1
answer
Self doubt:TOC
$L_{1}$ is recursive language and $L_{2}$ is recursively enumerable language. Then what will be $(1)$ $L_{1}\cup L_{2}=?$ $(2)$ $L_{1}\cap L_{2}=?$ $(3)$ $Decidable\cup undecidable=?$ $(2)$ $decidable\cap undecidable=?$
asked
Aug 23
in
Theory of Computation
by
srestha
(
1k
points)

82
views
theoryofcomputation
0
votes
1
answer
GATE forum sectional test Sefdoubt #TOC
$L = \{xyx,y\in\Sigma^*, n_a(x) = n_b(y)\}$ What is the class of this language? context sensitive context free regular none of the above why is this not CFL?
asked
Aug 23
in
Theory of Computation
by
intgate
(
9
points)

96
views
selfdoubt
theoryofcomputation
0
votes
2
answers
Pumping Lemma, self doubt
Is it necessary for the CFL string lenghts to be in AP if the alphabet is a singleton set?
asked
Aug 21
in
Theory of Computation
by
xiuhan
(
13
points)

65
views
pumpinglemma
theoryofcomputation
selfdoubt
0
votes
1
answer
self doubt on p and np problem
does P=NP ? a)decidable b)undecidable also please explain why it is decidable or undecidable.
asked
Aug 19
in
Theory of Computation
by
abhijeet at
(
9
points)

46
views
theoryofcomputation
turingmachine
decidability
0
votes
1
answer
Chomsky Classification
which grammars of Chomsky Classification allows (S → ε) in its production rules ?
asked
Aug 19
in
Theory of Computation
by
Akshay sinha
(
9
points)

33
views
theoryofcomputation
contextfreelanguages
contextsensitivelanguages
0
votes
1
answer
self doubt on regular languages
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
in
Theory of Computation
by
abhijeet at
(
9
points)

34
views
regularlanguage
theoryofcomputation
finiteautomata
0
votes
1
answer
ACE test doubtTOC
$S\rightarrow aABc$ $A\rightarrow b$ $B\rightarrow bAaB$ Will it generate regular grammar? As it generate string in form $aba^{*}bbc$, so it generate regular language. But not regular grammar. right?Because it is left linear and right linear both . So, it ... type3 grammar. right? Someone confirm. $S\rightarrow AB$ $A\rightarrow aAa$ $B\rightarrow bAb$ Is it regular grammar?
asked
Aug 15
in
Theory of Computation
by
srestha
(
1k
points)

23
views
theoryofcomputation
0
votes
2
answers
SelfDoubt #TOC Subset Operation.
I recently read that, subset operation is NOT closed under Reg Languages. Can anyone give me one intuitive example of Why So?
asked
Aug 15
in
Theory of Computation
by
mamtuj
(
25
points)

18
views
selfdoubt
theoryofcomputation
0
votes
1
answer
Made Easy Test Series TopicWise
asked
Aug 11
in
Theory of Computation
by
Mellophi
(
359
points)

76
views
madeeasytestseries
theoryofcomputation
0
votes
1
answer
Made Easy Test Series
Can anyone Explain or provide the complete methodology
asked
Aug 6
in
Theory of Computation
by
prajjwalsingh_11
(
13
points)

43
views
theoryofcomputation
regularexpressions
madeeasytestseries
0
votes
1
answer
What to read series
Can anyone tell me the book full name(all 3 if possible) and edition it is? The screenshot is from what to read series version 3.1
asked
Aug 2
in
Theory of Computation
by
Sourav Kar
(
5
points)

23
views
theoryofcomputation
0
votes
0
answers
Deterministic Finite Automata
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 states is 2n I want to understand the logic behind this generalized formula. How did we come to this conclusion?
asked
Aug 1
in
Theory of Computation
by
aryashah2k
(
2
points)

31
views
finiteautomata
theoryofcomputation
automata
dfadesign
0
votes
0
answers
Ace academy test series theroy of computation
L1={WWʳ w€(a+b)*} L2= Reversal(L1) What is L1.L2? What is the answer to this question please don't apply closure property I understood through closure property. My doubt is L1.L2 =W.Wʳ.Wʳ.W and this isn't accepted by any pda so shouldn't the answer be not cfl ??
asked
Jul 31
in
Theory of Computation
by
Aman kumar jha
(
5
points)

36
views
theoryofcomputation
aceacademytestseries
0
votes
0
answers
Theory Of Computation, Decidability, Rice's Theorem
asked
Jul 30
in
Theory of Computation
by
pranavsettaluri9
(
5
points)

13
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
ricestheorem
0
votes
0
answers
#Turing Machine
L={<M>M is a TM and L(M) = 2 } L is Recursive or Recursively Enumerable or Not Recursively Enumerable? why?
asked
Jul 28
in
Theory of Computation
by
Raj_81
(
11
points)

23
views
theoryofcomputation
turing
machine
0
votes
0
answers
Finite Languages and Automata Theory
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 ... 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
in
Theory of Computation
by
aryashah2k
(
2
points)

33
views
theoryofcomputation
finiteautomata
dfadesign
automata
0
votes
0
answers
Gate2008IT200832
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
in
Theory of Computation
by
prajjwalsingh_11
(
13
points)

23
views
theoryofcomputation
finiteautomata
regularexpressions
ardenstheorem
0
votes
1
answer
Finiteautomata
S1: Epsilon nfa has more than one initial state S2: Nfa has more than one initial state Which of the above is true and which of the above is false?
asked
Jul 15
in
Theory of Computation
by
Hrishi00
(
5
points)

32
views
nfadfa
theoryofcomputation
+2
votes
1
answer
Made Easy Test Series
Let L1 be decidable language and L2 be turing recognizable but not decidable language, then – L2/L1 is turing recognizable L1/L2 is decidable language Number of correct statements _?
asked
Jul 15
in
Theory of Computation
by
Kindaichi
(
4
points)

106
views
madeeasytestseries
toclanguages
theoryofcomputation
turingmachine
0
votes
0
answers
TOC(self doubtclassification into the language)
Came to read and also got to know as a shortcut about classification of a Language on the basis of the comparisons into CFL or CSL.Is it really the standard method or is it the short trick or just an illdefined way of attempting a question. This post can be taken as a reference – https://gateoverflow.in/26952/%23toc
asked
Jul 13
in
Theory of Computation
by
prajjwalsingh_11
(
13
points)

11
views
theoryofcomputation
pumpinglemma
contextfreelanguages
contextsensitivelanguages
0
votes
1
answer
Length of String and Properties
If E={a,b} and n=2 where n is length of a string, then number of even and odd length palindrome of length n will be?Can someone help please?
asked
Jul 8
in
Theory of Computation
by
athenahermes
(
5
points)

13
views
theoryofcomputation
strings
0
votes
1
answer
Context Free Language
Is this CFL? L = {wcwr  w, c ϵ {0,1}+ and c = 2}
asked
Jul 1
in
Theory of Computation
by
sameer2009
(
5
points)

16
views
theoryofcomputation
contextfreelanguages
+1
vote
1
answer
pushdown automata #CFL
Is the following language contextfree language(CFL) or not? If yes, then is it DeterministicCFL (DCFL)? L={ $a^i b^j$ where $i\neq 2*j+1$ and $j \geq 1$ and $i\geq 1$ }
asked
Jun 28
in
Theory of Computation
by
rgoyal
(
11
points)

44
views
theoryofcomputation
pushdownautomata
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
Jun 26
in
Theory of Computation
by
roh
(
9
points)

32
views
theoryofcomputation
gatebook
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
(
35
points)

19
views
theoryofcomputation
peterlinz
contextfreelanguages
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
(
7
points)

22
views
theoryofcomputation
Page:
1
2
3
4
...
15
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.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
Recent Blog Comments
Thanks, Can you tell me till when this might get...
8,589
questions
2,831
answers
13,617
comments
95,549
users