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
2
answers
theory of computation
hi guys, I have a doubt if two DFA accept the same set of language then are they equal? why or why not? answer really appreciated
answered
3 days
ago
in
Theory of Computation
by
shweta._.5
(
71
points)

40
views
toclanguages
finiteautomata
0
votes
0
answers
Self Doubts..
What would be the minimum number of states in a DFA on {a,b} where number of a's is divisible by 2 OR number of b's divisible by 3?
asked
Oct 23
in
Theory of Computation
by
Sinchit
(
15
points)

39
views
dfadesign
0
votes
0
answers
Testbook.com Test Series
Let L, M be any two Context Free Languages and X be a Regular Language. Which of the following statements given below are always correct ? A.) M – X is Context Free. B.) L $\cap$ M is Regular Language. C.) L $\cup$ M is Context Free. D.) M – X is Context Sensitive Language.
asked
Oct 22
in
Theory of Computation
by
Rishav Chetan
(
5
points)

14
views
0
votes
2
answers
Self Doubt: Topic Name Decidability
L = { <M> L(M) Contains at least 21 members} Where M = Turing machine Is this language Undecidable and if so how?
answered
Oct 22
in
Theory of Computation
by
spike500
(
17
points)

25
views
selfdoubt
0
votes
0
answers
Gate Overflow Test
gateoverflowtest:DeterministicPushdownAutomata accepting by empty stack accepts all DeterministicContextFreeLanguages having prefix property. Regular languages having prefix property is a subset of DeterministicContextFreeLanguages having prefix property. can anyone explain what actually that means.
asked
Oct 22
in
Theory of Computation
by
Vaibhav98
(
5
points)

20
views
gatepreparation
0
votes
0
answers
Theory of computer science
regular language closed under intersection with any language true or false
asked
Oct 20
in
Theory of Computation
by
nihal singh parihar
(
5
points)

26
views
0
votes
0
answers
Self Doubt in Theory of Computation, Regular Language
asked
Oct 19
in
Theory of Computation
by
nvs16
(
9
points)

47
views
selfdoubt
toclanguages
0
votes
0
answers
Peter Linz 5th edition
Find grammars for the following languages on ∑ = {a}, L = {w : w mod 3 > 0}.
asked
Oct 19
in
Theory of Computation
by
PrinceSoni
(
5
points)

8
views
peterlinz
0
votes
0
answers
https://www.tutorialspoint.com/automata_theory/undecidable_languages.htm
asked
Oct 18
in
Theory of Computation
by
killCode47
(
5
points)

11
views
0
votes
1
answer
GeeksforGeeks
The regular expression 0*(10*)* denotes the same set as (A) (1*0)*1* (B) 0 + (0 + 10)* (C) (0 + 1)* 10(0 + 1)* (D) none of these
answered
Oct 11
in
Theory of Computation
by
iarnav
(
231
points)

26
views
gate
0
votes
1
answer
Test series TOC question
Is L={uv / u=v & u ≠v & u,v ϵ {a,b}* } a CFL? If yes then can you design a PDA for it.
answered
Oct 11
in
Theory of Computation
by
iarnav
(
231
points)

24
views
0
votes
0
answers
thoery of computation
What is the difference between cross product,concatenation or union in thoery of computation and when to use them?
asked
Oct 9
in
Theory of Computation
by
Musa
(
5
points)

17
views
0
votes
1
answer
Finding number of equivalence class for a finite automata
answered
Oct 9
in
Theory of Computation
by
iarnav
(
231
points)

33
views
0
votes
1
answer
GATEBOOK TEST SERIES  TM Q4
Consider the following three statements. I. If the language L is recognized by a nondeterministic finite automaton, then L is recognized by a deterministic finite automaton. II. If the language L is recognized by a nondeterministic pushdown automaton, then L is ... (D) One of the three statements is known to be true; the other two statements are known to be false.
answered
Oct 9
in
Theory of Computation
by
iarnav
(
231
points)

52
views
gatebook
0
votes
1
answer
Design NFA (without ε moves) for the regular language that consist of all strings with at least two consecutive 0's
answered
Oct 9
in
Theory of Computation
by
spike500
(
17
points)

25
views
0
votes
1
answer
Construct regular expression for the language that consists of all strings ending with 00. Assume Σ= {0, 1}.
answered
Oct 9
in
Theory of Computation
by
spike500
(
17
points)

35
views
0
votes
0
answers
GATEBOOK TEST SERIES  TM
is a language and is a Turing machine which accepts . loops on epsilon forever. Which one of the following statements is true ? (A) is r.e but not recursive (B) can be non r.e (C) can not be recursive (D) can be regular
asked
Oct 7
in
Theory of Computation
by
Gate2022
(
7
points)

21
views
gatebook
0
votes
1
answer
GATEBOOK  Test Series  TOC
Consider the following problems. 1. Given a TM M and a string w, does M ever write the symbol ... of the above problems are decidable? (A) Only 4 (B) 2 and 3 Only (C) 2 and 4 Only (D) 2, 3 and 4 Only
answered
Oct 7
in
Theory of Computation
by
g21
(
1k
points)

21
views
gatebook
0
votes
2
answers
GATEBOOK  Test Series  TOC
Consider the following statements S1: If F is a finite language and L is some language, and is a regular language, then L must be a regular language. S2: If A is regular and is regular then so is B. Which one of the following statements is True ? (A) Only S1 (B) Only S2 (C) Both S1 and S2 (D) Neither S1 or S2
answered
Oct 7
in
Theory of Computation
by
g21
(
1k
points)

92
views
gatebook
0
votes
1
answer
madeeasy topicwise
C = {x  x is a binary string and decimal of any prefix of x is not of the form 3m+2 , where m>=0 } Is ir true or false ? The sol is given as true but I am getting it false plz correct.
answered
Oct 7
in
Theory of Computation
by
Arkaprava
(
711
points)

40
views
regularlanguage
0
votes
1
answer
self doubt toc
(0+1)*01(0+1)* + 1*0* = (0+1)* How is this regular expression equivalent to expression at rhs ? As ,at rhs we can get epsilon but in lhs we cant get epsilon ...
answered
Oct 6
in
Theory of Computation
by
Shashank Rustagi
(
513
points)

40
views
selfdoubt
0
votes
0
answers
GATEBOOK Test Series  TOC
Let h be the homomorphism defined by h(a) = b and h(b) = a. Let Which of the following statements is correct? (A). L is regular. (B). L is non regular DCFL (C). L is nonDCFL But CFL (D). L is NonCFL
asked
Oct 2
in
Theory of Computation
by
Gate2022
(
7
points)

20
views
gatebook
0
votes
0
answers
GATEBOOK Test Series  Closure Properties
Consider the following statements : 1. if a deterministic finite automaton M over alphabet accepts all strings of length less than or equal to the number of states in M, then it must accept all strings over . 2. if a nondeterministic finite automaton M over alphabet ... of the above statements is/are correct ? A. Only 3 B. Only 1,3,4 C. Only 1,2,3 D. ALL
asked
Oct 2
in
Theory of Computation
by
Gate2022
(
7
points)

19
views
gatebook
0
votes
0
answers
GATEBOOK  Test Series  TOC
Consider the CFG 'G' given below ,where S and A are nonterminals, S is the start symbol, and {0,1} is the set of terminals. Let L(G) denote the language generated by the above grammar, language L(G) is (A) Regular (B) DCFL but not Regular (C) CFL but not DCFL (D) CSL but not CFL
asked
Oct 2
in
Theory of Computation
by
Gate2022
(
7
points)

12
views
gatebook
0
votes
0
answers
Self Doubt Theory of ComputationHow to distinguish when to use cross product, concatenation or Union in DFA?
asked
Oct 2
in
Theory of Computation
by
the_dalela
(
5
points)

8
views
finiteautomata
0
votes
0
answers
#TOC SELF DOUBT ISI 2014
L IS SUBSET OF {A,B}* AND If L* is regular, then is L regular? JUSTIFY YOUR ANSWER.
asked
Oct 2
in
Theory of Computation
by
iarnav
(
231
points)

8
views
selfdoubt
toclanguages
0
votes
0
answers
TOC self doubt
L={ a^m b^n  m,n>=0} We know above language is regular as it doesn’t need any comparisons…. But Here L={ϵ, a,b,abb,aab,aabbb………...} If we take aabbb and if we apply Pumping Lemma by taken u=a, v=ab and w=bb let i=1 then we get aababbb which will not be in given language then how come it is regular? Where am i going wrong?
asked
Sep 30
in
Theory of Computation
by
Pathki Shivamsh
(
9
points)

15
views
toclanguages
0
votes
2
answers
Applied test series
Minimum number of States in a DFA , that accepts all strings of 0s and 1s ,whose integer equivalent are not divisible by 2 OR 3
answered
Sep 29
in
Theory of Computation
by
iarnav
(
231
points)

53
views
0
votes
2
answers
Ace academy test series
answered
Sep 29
in
Theory of Computation
by
iarnav
(
231
points)

51
views
0
votes
0
answers
#TOC Whether give languages are DCFL or just CFL?
Please explain for all these 4 languages about which of them are DCFL and which are just CFL only? Thank you.
asked
Sep 29
in
Theory of Computation
by
iarnav
(
231
points)

8
views
toclanguages
0
votes
0
answers
TOC self doubt
How to prove L={a ^n^2:n≥0} is not context free using Pumping Lemma?
asked
Sep 28
in
Theory of Computation
by
Pathki Shivamsh
(
9
points)

13
views
pumpinglemma
0
votes
0
answers
TOC Self Doubt
L1= a^n b^n n>=0 L2=ww^r  w ϵ (a+b)* what will be the prefix(L1),Suffix(L1) and prefix(L2),Suffix(L2) ??? Please Explain in detail
asked
Sep 26
in
Theory of Computation
by
Pathki Shivamsh
(
9
points)

20
views
toclanguages
0
votes
0
answers
# MadeEasy test
asked
Sep 26
in
Theory of Computation
by
raviranjan21
(
5
points)

23
views
0
votes
1
answer
Self Doubt  ME Notes (TOC)
Construct the minimal DFA for the following $\epsilon$ NFA NOTE: No need to give a complete explanation. Just provide me the final answer whatever you are getting means the number of states and the name of the states.
answered
Sep 22
in
Theory of Computation
by
Ehraz Hasan
(
366
points)

31
views
nfadfa
0
votes
0
answers
properties of regular language
Question let Σ = {1, 2}, Let L1 = {1^n 2^m 1^n+m  n ≥ 0, m ≥ 0}. show that L1 is not a regular language. Proof: Assume L1 is regular. We know that language L2 = {2^n1^n  n ≥ 0} is not a regular ... expression 2*1*. Since regular languages are closed under intersection, Hence L1 is not regular. is the above proof correct if not what modification i need to do
asked
Sep 21
in
Theory of Computation
by
prince123
(
5
points)

20
views
0
votes
0
answers
TheoryofComputation PDA (Self Doubt)
Can we construct PDA for the given Language: L = {a^i b^j c^k d^l } where i = k, j = l
asked
Sep 20
in
Theory of Computation
by
iot_ts
(
5
points)

24
views
0
votes
0
answers
made easy test series
Answer to the above question is incorrect I think can anyone please confirm it? Explanation given is incorrect
asked
Sep 19
in
Theory of Computation
by
Nishinoya
(
5
points)

36
views
0
votes
0
answers
Peter Linz Ex 8.1
https://gateoverflow.in/123323/peterlinzexercise81 Can someone help me with this question? It is CFL or not?
asked
Sep 18
in
Theory of Computation
by
Ehraz Hasan
(
366
points)

27
views
#peterlinz
0
votes
0
answers
#toc#zeal test series #cfl
Why 3 language is a CFL,please explain?
asked
Sep 18
in
Theory of Computation
by
Syywyeye
(
5
points)

29
views
0
votes
0
answers
made easy test series
if L1 is regular and L2 is DCFL then (L1 intersection L2*)’ is what a)CFL b)CSL c)recursive d)REL options given are b,c,d but if we apply * to any language it becomes regular language then (regular intersection regular) is regular so option should be “all are correct”. Can any one please explain?
asked
Sep 18
in
Theory of Computation
by
arnavd83
(
5
points)

29
views
#dcfl
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
2020 Oct 26  Nov 01
Ashutosh777
74 Points
shweta._.5
71 Points
mayureshpatle
66 Points
SarathBaswa
60 Points
vizzard110
8 Points
user2525
6 Points
rish1602
4 Points
siddharths067
4 Points
Shivateja MST
4 Points
RasMalai
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
Recent Blog Comments
Thanks, Can you tell me till when this might get...
Recent questions and answers in Theory of Computation
8,438
questions
2,715
answers
13,242
comments
95,460
users