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 #toc
+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)

41
views
#toc
theoryofcomputation
#testseries
#dfa
0
votes
0
answers
Mealy and moore machine are in syllabus of GATE?
Mealy and moore machine are in syllabus of GATE? Not found in syllabus broucher as well as in previous years questions. If yes, please provide if any question arrived in previous 10 years.
asked
May 15
in
Theory of Computation
by
Cser
(
6
points)

5
views
#update
#toc
#gate
#syllabusdoubt
#2021
0
votes
0
answers
#Gate 2021#TOC
Assertion reasoning question: Assertion(a) : Let L is recursive enumerable language and problem X is defined as X: Is L=Φ? is not recursively enumerable Reasoning(r): X violates the condition that says. if L is an infinite set in S, a set of recursive enumerable ... r is not the correct reason for a a is true , r is false a is false, r is true Please answer with explanation
asked
May 13
in
Theory of Computation
by
sushmitagoswami
(
14
points)

6
views
#gatepreparation
#toc
0
votes
0
answers
GATE # 2021 #TOC
Let X be defined as follows: X: Given M an encoding of a Turing Machine. Does M halt on all inputs? Which of the following is true? X is decidable X is undecidable but partially decidable X is undecidable and not even partially decidable X is not a decidable problem Please answer with explaination.
asked
May 13
in
Theory of Computation
by
sushmitagoswami
(
14
points)

3
views
#help
#gatepreparation
#toc
0
votes
0
answers
#Gate 2021 #TOC
Which if the following is false? L is recursive if and only if it is generated by some TM in canonical order L is recursively enumerable if and only if there exist a TM which generates L is context sensitive if and only if it is generated by some TM in canonical order None of these. Please answer with explanation.
asked
May 13
in
Theory of Computation
by
sushmitagoswami
(
14
points)

3
views
#help
#gatepreparation
#toc
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
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
(
6
points)

6
views
theoryofcomputation
#toc
0
votes
0
answers
How to solve this problem using state elimination method?
asked
Apr 24
in
Theory of Computation
by
g2021
(
6
points)

12
views
#help
#toc
#dfa
0
votes
0
answers
Self Doubt Push Down Automata in Theory of Computation
asked
Apr 19
in
Theory of Computation
by
jainpawan21
(
8
points)

4
views
#pda
#toc
0
votes
0
answers
TOCWhich of the following is true?
L1={a^n b^m:n>=0,m<n} L2={a^3n b^2n : n>2} L3={a^n b^m: m<=n3 or m=n1} i>L1 U L2 IS A DCFL ii>L1 L2 IS A DCFL iii>L3 is a DCFL. Please verify which of the following is true?
asked
Apr 1
in
Theory of Computation
by
Doraemon
(
115
points)

6
views
#toc
0
votes
1
answer
Regular Languages self doubt
What is the language given by this : ${\color{Red} {a^mb^nLCM(m,n)<=1}}$
asked
Mar 9
in
Theory of Computation
by
Abhipsa
(
26
points)

14
views
theoryofcomputation
#toc
#regularlanguage
0
votes
0
answers
Made easy work book toc
Why aa*(bb*a)* not a regular expressian for starting and ending with symbol A Dfa
asked
Feb 25
in
Theory of Computation
by
Ritesh123
(
6
points)

15
views
madeeasyworkbook
#toc
0
votes
1
answer
Automata  DFA
In what cases we need to include epsilon in DFA.
asked
Feb 18
in
Theory of Computation
by
pppankajsaini
(
8
points)

27
views
#dfa
theoryofcomputation
#toc
+1
vote
0
answers
Turing Machine
As per the definition of a Turing Machine, it does not accept Epsilon. But, A → ϵ can be generated by a Unrestricted Grammar. So, how can we say that Turing Machines are the acceptors for Recursively Enumerable languages generated by Unrestricted Grammar?
asked
Feb 13
in
Theory of Computation
by
Joon88
(
7
points)

22
views
#toc
turingmachine
theoryofcomputation
grammar
unrestrictedgrammar
+1
vote
0
answers
TOC(self doubt)
How is the complement of $L=\{ww w \epsilon(a+b)^*\}$ is $CFL$
asked
Feb 5
in
Theory of Computation
by
Pratyush Priyam Kuan
(
804
points)

23
views
theoryofcomputation
#closureproperties
#toc
0
votes
0
answers
Applied course test series : Turing machine
Can someone explain statement I. My doubt is that if the language is accepted and rejected both by turing machine then it is decidable language which also recognized by Turing machine. So statement I should be false ,right?
asked
Jan 29
in
Theory of Computation
by
vishal burnwal
(
135
points)

71
views
#toc
0
votes
0
answers
SELF DOUBT: PREVIOUS GO COMPILERS
How to solve these types of questions quickly? is there any algorithm?
asked
Jan 23
in
Theory of Computation
by
Debapaul
(
699
points)

28
views
#toc
0
votes
0
answers
made easy test series DPDA doubt
asked
Jan 23
in
Theory of Computation
by
Dheeraj Varma
(
22
points)

14
views
madeeasytestseries
#toc
#pda
0
votes
0
answers
made easy test series DPDA doubt
Why II. is invalid??
asked
Jan 23
in
Theory of Computation
by
Dheeraj Varma
(
22
points)

18
views
madeeasytestseries
#toc
#pda
0
votes
1
answer
Gate 1992 Question
In which of the cases stated below is the following statement true? “For every nondeterministic machine M1, there exists an equivalent deterministic machine M2 recognizing the same language“. (a) M1 is a nondeterministic finite automaton (b) M1 is a nondeterministic PDA (c) M1 is a nondeterministic Turing machine (d) For no machine M1 use the above statement true
asked
Jan 20
in
Theory of Computation
by
veenashiva18
(
7
points)

109
views
#toc
#turingmachine
0
votes
0
answers
Self Doubt #regular languages
What is PHI in Finite Machine representation, is it an isloated state ? , and how come the below is true ∅ ∗ = epsilon
asked
Jan 20
in
Theory of Computation
by
dr_Jackal
(
16
points)

6
views
#toc
#regularexpression
+1
vote
0
answers
ME CBT How is "A" regular?
asked
Jan 17
in
Theory of Computation
by
toxicdesire
(
305
points)

37
views
madeeasytestseries
#toc
0
votes
1
answer
Consider L = {a^n b^n c^n n ≥ 0}. Is L'(L Complement) a CFL? Prove it.
asked
Jan 16
in
Theory of Computation
by
bankeshk
(
12
points)

26
views
#toc
contextfreelanguage
#testseries
0
votes
0
answers
Madeeasy test series  How many lookaheads are present?
asked
Dec 31, 2019
in
Compiler Design
by
luc_Bloodstone
(
38
points)

13
views
madeeasytestseries
compilerdesign
#toc
0
votes
1
answer
Self Doubt TOC Decidability
L = { M  M is TM and L(M) is infinite. This is not recursive but is this semi decidable or Not?
asked
Dec 30, 2019
in
Theory of Computation
by
tp21
(
269
points)

28
views
#toc
decidability
0
votes
1
answer
Self doubt on identify language
What is a^m b ^ n where m* n= p ?
asked
Dec 28, 2019
in
Theory of Computation
by
Winner
(
73
points)

39
views
#toc
0
votes
0
answers
Madeeasy Test Series  SSA form
Doubt : In solution they used a variable more than once in LHS but in SSA form I think we always use new variable in LHS. Solution they have given:
asked
Dec 25, 2019
in
Compiler Design
by
luc_Bloodstone
(
38
points)

20
views
madeeasytestseries
compilerdesign
#toc
0
votes
1
answer
Self dount TOC
1. Complement of RE which is not REC is __ 2. Complement of RE which is also REC is __
asked
Dec 24, 2019
in
Theory of Computation
by
Chirag Shilwant
(
181
points)

18
views
#toc
theoryofcomputation
#closureproperties
recursive
0
votes
0
answers
DFA/NFA MINIMUM NUMBER OF STATES
How to decide minimum when will DFA have N+2 or N+1 states? https://gateoverflow.in/39562/gate2016216 https://gateoverflow.in/8256/gate2015253 https://gateoverflow.in/118302/gate2017122 https://gateoverflow.in/118160/gate2017225 above 2 are cases for N+1 and latter are N+2
asked
Dec 6, 2019
in
Theory of Computation
by
Asim Siddiqui 4
(
8
points)

8
views
theoryofcomputation
finiteautomata
#dfa
#toc
0
votes
0
answers
String acceptance in PDA
In PDA is it okay that stack is not empty but string reached the final state? Can we accept such string?
asked
Dec 2, 2019
in
Theory of Computation
by
luc_Bloodstone
(
38
points)

14
views
theoryofcomputation
#toc
pushdownautomata
0
votes
1
answer
Self doubt on a Decidability question
For arbitrary CFG G and arbitrary regular expression R, whether L(R)$\subseteq $L(G) is DECIDABLE ?
asked
Nov 18, 2019
in
Theory of Computation
by
pranay562
(
926
points)

24
views
#toc
#decidability
0
votes
0
answers
SelfDoubt: GATE questions
https://gateoverflow.in/302841/gate20197 Can anyone give some example, to show where is difference between option A) and B)?
asked
Nov 18, 2019
in
Theory of Computation
by
srestha
(
739
points)

29
views
#toc
0
votes
0
answers
REGULAR EXPRESSIONS SELF DOUBT
Through which transformations I could prove that RE (a+b+c)* is equivalent to (a*b*+c*)* ,I tried some transformations on (a+b+c)* but getting this ((a*b*)*+c*)*
asked
Nov 16, 2019
in
Theory of Computation
by
codingo1234
(
7
points)

20
views
#toc
0
votes
0
answers
Self doubt on decidability in pda
Why checking whether 2 pdas equal or not is undecidable?
asked
Nov 15, 2019
in
Theory of Computation
by
Winner
(
73
points)

23
views
#toc
0
votes
1
answer
TOC questions
Give brief ans
asked
Nov 14, 2019
in
Theory of Computation
by
amit166
(
139
points)

53
views
#toc
0
votes
1
answer
CS_GATE_2020_07 ( TOC )
asked
Nov 9, 2019
in
Theory of Computation
by
Priyansh Singh
(
257
points)

28
views
#toc
0
votes
0
answers
Self doubt (T O C)
A grammar can be ambiguous if it represents NonDeterministic Model.
asked
Nov 8, 2019
in
Theory of Computation
by
Priyansh Singh
(
257
points)

12
views
#toc
0
votes
1
answer
Self Doubt (T.o.c)
What is Minimal dfa for → (0*1+1*)
asked
Nov 8, 2019
in
Theory of Computation
by
Priyansh Singh
(
257
points)

30
views
#dfa
#toc
0
votes
0
answers
Some gate questions (TOC)
A is recursive if both A and its complement are accepted by Turing Machine. True or false ?
asked
Nov 7, 2019
in
Theory of Computation
by
Priyansh Singh
(
257
points)

14
views
#toc
#recursive
Page:
1
2
3
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
Jun 2020
ummokkate
8 Points
nehaPal13
7 Points
Taraka
6 Points
pratyush12
6 Points
Radheram
6 Points
vps123
4 Points
reboot
2 Points
Chinmay Agnihotri
2 Points
Shubham Aggarwal
2 Points
Musa
1 Points
7,410
questions
1,744
answers
10,718
comments
90,372
users