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
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)

26
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)

37
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)

44
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)

11
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)

19
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)

21
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
(
7
points)

19
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)

27
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)

23
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)

27
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)

21
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)

23
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)

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

10
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.2k
points)

26
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.2k
points)

32
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)

18
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)

19
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
(
7
points)

9
views
toclanguages
peterlinz
grammar
dfas
pumpinglemma
0
votes
1
answer
Does Left recursive grammar same as left linear grammar
answered
Jan 17
in
Theory of Computation
by
wander
(
301
points)

14
views
selfdoubt
0
votes
0
answers
An introduction to formal languages and automata peter linz
asked
Jan 16
in
Theory of Computation
by
kirtipurohit
(
7
points)

26
views
toclanguages
peterlinz
grammar
dfas
nfadfa
0
votes
0
answers
Peter Linz 5e Ex2.1 Q7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)n_{b}(w))mod3>0$ }
[closed]
asked
Jan 14
in
Theory of Computation
by
aditi19
(
53
points)

10
views
peterlinz
toclanguages
dfas
+1
vote
0
answers
Peter Linz 5e Ex2.1 Q7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)n_{b}(w))mod3>0$ }
asked
Jan 14
in
Theory of Computation
by
aditi19
(
53
points)

29
views
peterlinz
toclanguages
dfas
0
votes
1
answer
Ace test series
[closed]
answered
Jan 7
in
Theory of Computation
by
Abhisheksmile94
(
347
points)

35
views
testseries
0
votes
0
answers
Ace Test Series
Is C Valid Answer? I feel regular expression in C can also Generate 11 which is not there in language so the answer should be D only….Is my reasoning valid if not please help to clear this concept...
asked
Jan 6
in
Theory of Computation
by
vipin.gautam1906
(
9
points)

37
views
dfadesign
0
votes
0
answers
Self doubt on decidability of turing machine and dfa
asked
Jan 5
in
Theory of Computation
by
meivinay
(
5
points)

58
views
decidability
turingmachine
selfdoubt
0
votes
1
answer
Applied Test Series TOC
Options: My answer was: D answer according to them was B and D and their explaination was
answered
Jan 4
in
Theory of Computation
by
Abhisheksmile94
(
347
points)

28
views
testseries
toclanguages
0
votes
0
answers
GATE 2003 , Theory Of Computation , Turing Machine
asked
Jan 4
in
Theory of Computation
by
Pushkar Khadase
(
5
points)

29
views
toclanguages
turingmachine
0
votes
1
answer
Theory of automata
Convert the Following DFA to Regular Expression using GNFA.
answered
Jan 3
in
Theory of Computation
by
Abhisheksmile94
(
347
points)

42
views
finiteautomata
toclanguages
0
votes
2
answers
TOC closure properties of RL
let L1=a^n (which is a regular language) and L2=b^n (which is also a regular language) L1.L2 is also regular.. how?? as (a^nb^n) is not a regular language
answered
Jan 3
in
Theory of Computation
by
Abhisheksmile94
(
347
points)

49
views
selfdoubt
toclanguages
0
votes
3
answers
youtube exercise unacademy
L1=a^n,,n>0 L2=a^n b^n c^n , n>0 L1.L2 is a)regular b)cfl c)csl d)none
answered
Jan 3
in
Theory of Computation
by
Abhisheksmile94
(
347
points)

44
views
toclanguages
0
votes
0
answers
My college homework
1) Let ∑ = {D , L}. Find a DFA that accepts Password (P) with the following conditions:   P  ≥ 4  P begins with a letter and ends with a letter.  P contains at least one digit. 2) Let ∑ = { 0..9 , ... the following DFA that has access to the laboratories of company controlled. The employee number becomes read as a binary number. Which employee numbers are accepted.
asked
Dec 29, 2020
in
Theory of Computation
by
MotasemMobayyed
(
5
points)

11
views
finiteautomata
0
votes
1
answer
KLP MISHRA #TOC #Precedence of operators #computaion
answered
Dec 23, 2020
in
Theory of Computation
by
Harshal Vora
(
11
points)

14
views
computation
theory
0
votes
0
answers
lIntroduction to Languages and The Theory of Computation
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)

12
views
grammar
0
votes
0
answers
Introduction to Languages and The Theory of Computation
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)

6
views
toclanguages
0
votes
0
answers
Introduction to Languages and The Theory of Computation John C. Martin North Dakota State University
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)

9
views
toclanguages
0
votes
0
answers
John C. Martin 4.9
4.9. Suppose that G1 = (V1, {a, b}, S1, P1) and G2 = (V2, {a, b}, S2, P2) are CFGs and that V1 ∩ V2 = ∅. a. It is easy to see that no matter what G1 and G2 are, the CFG Gu = (Vu, {a, b}, Su, Pu) defined by Vu = V1 ∪ V2, Su = S1, and Pu = P1 ∪ ... {S1 → S1S1  } generates every string in L(G1) ∗. Find a grammar G1 with V1 = {S1} and a string x ∈ L(G ∗ ) such that x /∈ L(G) ∗.
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)

7
views
datastructures
0
votes
0
answers
Introduction to Languages and The Theory of Computation John C. Martin
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)

8
views
toclanguages
0
votes
1
answer
This was asked in ace academy test series, but no suitable explaination was provided. Kindly enlighten!
answered
Dec 22, 2020
in
Theory of Computation
by
Deepakk Poonia (Dee)
(
1.5k
points)

35
views
toc
0
votes
1
answer
#selfdoubt #regular_toc_languages
answered
Dec 21, 2020
in
Theory of Computation
by
Sahil91
(
683
points)

26
views
selfdoubt
toclanguages
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 Feb 22  28
Enolx.21
12 Points
rapidxy
9 Points
zxy123
6 Points
adas7099
4 Points
Shinichi_Kudo
2 Points
Deepakk Poonia (Dee)
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,095
questions
3,154
answers
14,583
comments
95,939
users