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 and answers in Theory of Computation
+1
vote
0
answers
Theory of computation  Pumping Lemma for CFL [Self Doubt]
asked
3 days
ago
in
Theory of Computation
by
hari0943
(
9
points)

10
views
pumpinglemma
0
votes
0
answers
Design Turing Machine for LANGUAGE L1=a*bb(a+b)*
asked
May 6
in
Theory of Computation
by
chris gyle
(
5
points)

9
views
turingmachine
+1
vote
0
answers
Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a leftlinear grammar for the language S→ abA A → baB B → aA  bb.
asked
May 3
in
Theory of Computation
by
Setsu
(
13
points)

9
views
peterlinz
toclanguages
peterlinz
+1
vote
0
answers
Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a leftlinear grammar for the language S→ abA A → baB B → aA  bb.
[closed]
asked
May 3
in
Theory of Computation
by
Setsu
(
13
points)

6
views
peterlinz
toclanguages
peterlinz
0
votes
0
answers
PhD Admissions Written Test (Basic)
For any language L, and for any k ≥ 0, let L k denote the language obtained by concatenating any k strings from L (note that L^0 = epsilon). Suppose L1 is a contextfree language and R is a regular language over the same alphabet Σ of size at least 3. The smallest value of k for which (R \ L1) k ∪ (L1 \ R) is not necessarily contextfree is
asked
May 2
in
Theory of Computation
by
Rashimdixit
(
9
points)

3
views
#cfl
0
votes
0
answers
Ullman,rozen
Levi Ackerman: Is L= {xwywr∣x, w,y∈(a+b) +} regular? wr is reverse of w
asked
May 2
in
Theory of Computation
by
Gogo6996
(
5
points)

5
views
toclanguages
0
votes
0
answers
Ambiguity in grammar
Show that the following grammar is ambiguous. S → aBab, A → aABa, B → ABbb.
asked
May 2
in
Theory of Computation
by
Sravanth0989
(
5
points)

3
views
ambiguity
0
votes
0
answers
Ambiguity of grammar
Show that the following grammar is ambiguous. S → aBab, A → aABa, B → ABbb.
asked
May 2
in
Theory of Computation
by
Sravanth0989
(
5
points)

3
views
selfdoubt
0
votes
0
answers
DFA construction
For E={a,b} construct a dfa for language L where L={w  w has a b in its 2nd last position if such a position exists}????
asked
May 2
in
Theory of Computation
by
harshit_1010
(
5
points)

3
views
dfas
toclanguages
0
votes
0
answers
madeeasys toc workbook
can somebody explain how to solve this type of questions
asked
Apr 26
in
Theory of Computation
by
jainanmol123
(
13
points)

18
views
selfdoubt
0
votes
1
answer
Book: Introduction to formal languages and automata by Peter LinzChapter 2: Finite AutomataExercises
answered
Apr 21
in
Theory of Computation
by
Konankun
(
71
points)

29
views
dfas
0
votes
0
answers
#DFA Introduction, Formal Languages, DFA Construction examples
asked
Apr 10
in
Theory of Computation
by
DarkShadow18
(
5
points)

18
views
toclanguages
0
votes
0
answers
AppliedGate lecture example
What is the NFA that does not accept strings ending “101” ?
asked
Apr 7
in
Theory of Computation
by
shri385
(
5
points)

16
views
nfadfa
toclanguages
finiteautomata
0
votes
0
answers
complement(ww) w ε {a,b)* is CFL or Not
complement(ww) w ε {a,b)* is CFL . BUt its Complement {www ε {a,b}*} is not CFL ?HOW?
asked
Apr 7
in
Theory of Computation
by
diptanshu malviya
(
5
points)

21
views
madeeasytest
+1
vote
1
answer
#Toc #Applied
For this type of question, how did you attempt to make the DFA?
answered
Mar 22
in
Theory of Computation
by
zxy123
(
3.6k
points)

24
views
computation
theory
0
votes
0
answers
Peter Linz An Introduction to Formal Languages and Automata 6th edition chapter 1.3 exercise 12
asked
Mar 17
in
Theory of Computation
by
cherryred1
(
5
points)

23
views
peterlinz
0
votes
0
answers
assignment for b.tech
Design turing machine that accepts all string containing at least one ‘a’ and ‘b’ where $\sum =(a,b,c)$
asked
Mar 12
in
Theory of Computation
by
amit166
(
87
points)

24
views
turingmachine
0
votes
1
answer
SELF DOUBT : What is the minimum DFA for (aa+aaa)* ?
answered
Mar 7
in
Theory of Computation
by
ascend
(
5
points)

27
views
dfas
0
votes
0
answers
PDA for a^nb^n/n>=1
Is this PDA correct for a^n. B^n/n>=1?
asked
Mar 4
in
Theory of Computation
by
jaswanth431
(
5
points)

20
views
toclanguages
+2
votes
1
answer
Self Doubt on Theory of Computation
What is the intersection of recursive and recursively enumerable language?
answered
Mar 4
in
Theory of Computation
by
zxy123
(
3.6k
points)

30
views
turingmachine
toclanguages
selfdoubt
+1
vote
1
answer
Unambiguous Grammar
I am no able to prove if the following grammar is ambiguous. G=({S,A,B},{A,B},P,S} P: S>aABbBA A>bSa B>aSb Can some one help me prove it?
answered
Mar 2
in
Theory of Computation
by
zxy123
(
3.6k
points)

33
views
selfdoubt
0
votes
0
answers
ACE Test Series
What is the minimum no of states in DFA which accepts the language generated by reg exp (0*1)*1(0+1)* ?. Is this binary strings containing 1? Pls Answer.
asked
Feb 9
in
Theory of Computation
by
akashks
(
5
points)

32
views
testseries
0
votes
1
answer
Context Free Languages (Self Doubt)
I understand that the language L = {a^m b^n c^k(m=n)or(n=k)} is CFL because it can be represented as the union of L1 = {a^m b^m c^k} and L2 = {a^m b^k c^k} which are both CFL's. But I can't figure out the working of the PDA accepting L. To check ... meaning (m=n) or (mn) a's or (nm) b's will remain in the stack meaning (m!=n). How can we check for (n=k) now?
answered
Feb 7
in
Theory of Computation
by
Ollie
(
525
points)

44
views
toclanguages
selfdoubt
0
votes
0
answers
Made easy test series
Consider the following problems and select the problem which is recursively enumerable but not recursive. (MSQ type) 1 . Whether a given Turing machine accepts nonempty language. 2. Whether a given Turing machine accepts finite language . 3. Whether a given Turing machine accepts at most 10 strings 4. Whether a given Turing machine accepts at least 10 strings.
asked
Feb 4
in
Theory of Computation
by
gajendercse
(
41
points)

48
views
decidability
selfdoubt
0
votes
0
answers
Practise Question from Ulman
Please give the DFA and regular expression
asked
Feb 4
in
Theory of Computation
by
chandra sai
(
5
points)

18
views
dfas
0
votes
0
answers
made easy test series
Answer given is “All of these” My answer is none of these are regular.
asked
Feb 3
in
Theory of Computation
by
rahul65
(
5
points)

25
views
toclanguages
0
votes
0
answers
ACE Test Series
$A. Regular$ $B. CSL but not CFL$ $C. CFL$ $D. CSL$ Solution given is
[closed]
asked
Feb 2
in
Theory of Computation
by
Parth27
(
163
points)

34
views
testseries
0
votes
0
answers
TOC Made easy
Consider the grammar consisting of seven productions. S → aA  aBB A → aaA  λ B → bB  bbC C → B After elimination of unit, useless, and λ productions how many productions remain in the resulting grammar ? 2 3 4 5
asked
Feb 2
in
Theory of Computation
by
kirtipurohit
(
15
points)

39
views
testseries
toclanguages
0
votes
0
answers
TOC  CSL Complement  Ace Pre Gate Question
The complemment of the language {wwwww is in (
[email protected]
+$)*} is Regular CSL but not CFL CFL CSL Answer Can someone please explain how this language is CFL ?
asked
Feb 1
in
Theory of Computation
by
Sam_Gate21
(
5
points)

30
views
selfdoubt
0
votes
0
answers
Gate Overflow itself
Is the explanation is correct? Linkhttps://gateoverflow.in/33183/complementofcsl If I say complement of $a^{n}b^{n}c^{n} \, \, \, \, \, \, is\, \, \, \, \, a^{n}b^{n}c^{m} \: \: and\: \: \: m\neq n$ Then How Can it be regular?
asked
Feb 1
in
Theory of Computation
by
RavGopal
(
145
points)

32
views
toclanguages
+1
vote
1
answer
Output Of Turing Machine : Ace Academy Subject Wise Test Series
answered
Feb 1
in
Theory of Computation
by
Parth27
(
163
points)

36
views
turingmachine
0
votes
0
answers
self doubt  decidability
L={<M> M is a TM that accepts all even numbers}. How to check whether it is RE, REC or not RE… I think Rice’s theorem 2nd part is not applicable here
asked
Feb 1
in
Theory of Computation
by
Abhineet Singh
(
23
points)

31
views
decidability
toclanguages
+1
vote
0
answers
Recursive Languages Self Doubt
Is recursive language closed under positive closure?
asked
Jan 29
in
Theory of Computation
by
aditi19
(
53
points)

36
views
toclanguages
+1
vote
1
answer
Applied AI ALL INDIA MOCK TEST
In option b, it can generate any string where a can be followed by b & then c or b followed by a & then c , c by a & then b i.e sequence od characters isn’t fixed. Does it have a CFG for it?
answered
Jan 25
in
Theory of Computation
by
Sahil91
(
683
points)

27
views
#cfl
0
votes
0
answers
Madeeasy Test series TOC Q1
asked
Jan 23
in
Theory of Computation
by
Shivateja MST
(
45
points)

22
views
toclanguages
+1
vote
1
answer
Peter Linz Ex7.3 Q6 CFL
L=$a^nb^{2n}  n\geq 0$ is a DCFL. Show that L* is DCFL
answered
Jan 23
in
Theory of Computation
by
zxy123
(
3.6k
points)

40
views
peterlinz
dcfl
+1
vote
1
answer
Made easy test series
Can anyone draw the DFA’s for the question mentioned?
answered
Jan 22
in
Theory of Computation
by
zxy123
(
3.6k
points)

35
views
finiteautomata
0
votes
0
answers
CFG Selfdoubt
As per the definition of CNF and GNF, these grammars doesn’t allows $\epsilon$ productions. What if the language contains $\epsilon$? In that case how do we convert the CFG to CNF and GNF? Can someone explain with an example?
asked
Jan 20
in
Theory of Computation
by
aditi19
(
53
points)

24
views
cfg
0
votes
1
answer
Show that the language S> aSS b is not regular ?
answered
Jan 20
in
Theory of Computation
by
SarathBaswa
(
849
points)

21
views
toclanguages
peterlinz
0
votes
0
answers
An introduction to formal languages and automata
How can I explain that this language L= { a<sup>n</sup> b<sup>l</sup> : n ≠ l } is not regular. [USE PUMPING LEMMA OR CLOSURE PROPERTIES] This question is under a book named An introduction to ... understandable manner and show how you exactly arrived at the solution? That would be a great help to me. Thanks in advance
asked
Jan 18
in
Theory of Computation
by
kirtipurohit
(
15
points)

10
views
toclanguages
peterlinz
grammar
dfas
pumpinglemma
To see more, click for all the
questions in this category
.
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
2021 May 10  16
hari0943
4 Points
aryavart
2 Points
Nikhil_dhama
2 Points
Shiva Sagar Rao
2 Points
Shaik Masthan
2 Points
Weekly Top User (excluding moderators) will get free access to
GATE Overflow Test Series for GATE 2021
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
Recent questions and answers in Theory of Computation
9,270
questions
3,204
answers
14,751
comments
96,304
users