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 and answers in Theory of Computation
0
votes
1
answer
Context Free Language
Is this CFL? L = {wcwr  w, c ϵ {0,1}+ and c = 2}
answered
7 hours
ago
in
Theory of Computation
by
RavGopal
(
48
points)

9
views
theoryofcomputation
contextfreelanguages
0
votes
0
answers
Decidability In TOC
Turing Machine accepts a regurlar language. Is it decidable or not ?
asked
3 days
ago
in
Theory of Computation
by
ajaybhardwaj1999
(
6
points)

9
views
+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$ }
answered
3 days
ago
in
Theory of Computation
by
RavGopal
(
48
points)

29
views
#toc
#pda
#cfl
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.
answered
5 days
ago
in
Theory of Computation
by
premu
(
69
points)

15
views
theoryofcomputation
0
votes
0
answers
Show that the language L = w1cw2 : w1, w2 ∈ {a, b}+ , {w1 ≠ w^R2 } with Σ = {a, b, c}, is contextfree.
asked
5 days
ago
in
Theory of Computation
by
roh
(
17
points)

10
views
theoryofcomputation
#gatebook
#toc
#peterlinz
0
votes
0
answers
In Compiler Construction course While mapping the conditions for the Shift and Reduce actions in SLR table
asked
6 days
ago
in
Theory of Computation
by
Arsalan Sheikh
(
6
points)

11
views
compiler
compilerdesign
compilerconstruction
0
votes
1
answer
Regular expression self doubt
Given is a Regular Expression, 0*(10*)* If we want ot generate strings from this regular language , then while generating a string do we need to keep value of * same for a string or can we change it for every digit in the regular expression. For eg ... 0^4(1 0^3)^6 in a string . Please answer this since, I am finding it difficult to solve these type of questions.
answered
Jun 23
in
Theory of Computation
by
Nikhil_dhama
(
87
points)

14
views
0
votes
0
answers
MINIMUM FINITE STATE MACHINE
Is it true that if we reverse the DFA twice and delete unreachable states in every step then we definitely get the minimum DFA always? i.e., DFA > REVERSE OF DFA AND REMOVE UNREACHABLE STATES > CONVERT IT INTO DFA HERE IT IS THE REVERSAL OF THE ... DOUBT IS , IS IT THE RESULTANT DFA IS ALWAYS MINIMUM DFA . IF SO , PLEASE GIVE AN IDEA TO AT LEAST CONVINCE ME .
asked
Jun 19
in
Theory of Computation
by
NARAYANA
(
7
points)

12
views
0
votes
0
answers
PDA construction
How to construct the PDA for the language on alphabet 0,1 which accept all the strings with number of 0's in the string is not equal to the number of 1's in the string ?
asked
Jun 17
in
Theory of Computation
by
NARAYANA
(
7
points)

4
views
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
(
57
points)

8
views
theoryofcomputation
peterlinz
contextfreelanguages
#toc
0
votes
0
answers
gfgpracticecontest
given ans is 3.anyone please minimize this step by step???
asked
Jun 11
in
Theory of Computation
by
Papun417
(
7
points)

6
views
0
votes
0
answers
Regular Expression
what is the regular expression for strings of length atmost 2 over {a,b}. Plz give detailed soln.
asked
Jun 11
in
Theory of Computation
by
Vaishalikashyap
(
10
points)

18
views
theoryofcomputation
0
votes
1
answer
regular expression
Regular expression for all strings starts with a or ending with b?
answered
Jun 11
in
Theory of Computation
by
Vaishalikashyap
(
10
points)

15
views
0
votes
0
answers
Peter Linz Theory of Computation Exercise 5.1 Question15
asked
Jun 11
in
Theory of Computation
by
aditi19
(
57
points)

10
views
theoryofcomputation
peterlinz
#toc
contextfreelanguages
0
votes
0
answers
TOC GATE201332 doubt regarding dcfl
$L2 = \left \{ 0^p1^q0^r ∣ p,q,r ≥ 0, p ≠ r \right \}$ Is the above language dcfl? The comments in the question state that it is but what about the case when #1’s = 0. Then how is the first half of 0’s separated from the second half of 0’s deterministically? Ref – https://gateoverflow.in/1543/gate201332
asked
May 30
in
Theory of Computation
by
abhijit_m
(
6
points)

13
views
usergate2013
usermod
theoryofcomputation
identifyclasslanguage
dcfl
0
votes
1
answer
TIFR2020B2
Consider the following statements . 1. The intersection of two context  free languages is always context  free . 2. The super  set of a context  free language is never regular. 3. The subset of a decidable language is always decidable . 4. Let $\sum$ = { a , b , c } . Let L$\subseteq$ ... ) and ( 3 ) ( d ) Only ( 4 ) ( e ) None of ( 1 ) , ( 2 ) , ( 3 ) , ( 4 ) are true
answered
May 26
in
Theory of Computation
by
Kushagra गुप्ता
(
415
points)

11
views
tifr2020
theoryofcomputation
0
votes
0
answers
PYQ GATE 2008
What will be the correct option ?
asked
May 19
in
Theory of Computation
by
Ananya2000
(
22
points)

8
views
0
votes
0
answers
PYQ GATE CS 2012
What will be the correct option for the above DFA ?
asked
May 19
in
Theory of Computation
by
Ananya2000
(
22
points)

5
views
0
votes
1
answer
Self Doubt from notes
What will be the language generated by the following grammar ? S → 0S1S / 1S0S/E P.S. – E is Epsilon
answered
May 18
in
Theory of Computation
by
toxicdesire
(
305
points)

15
views
+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)

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

6
views
#update
#toc
#gate
#syllabusdoubt
#2021
0
votes
0
answers
University of Chicago exam for formal Language
I got the following questions in my exam last week but I am not sure about the answers. Here are my answers. Can anyone verify if my answers are right of wrong? false false true true false false false false true false E
asked
May 15
in
Theory of Computation
by
rj865200
(
6
points)

7
views
0
votes
1
answer
#Gate 2021#TOC
Which of the following properties of recursive enumerable set is/are recursive enumerable L = Φ L contains at least 5 members L has exactly one member Please explain
answered
May 14
in
Theory of Computation
by
shashin
(
1.9k
points)

18
views
#gatepreparation
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)

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

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

4
views
#help
#gatepreparation
#toc
0
votes
0
answers
l1 = (ab m>0), l2=lamda. then l is which type of language  regular or context?
asked
May 13
in
Theory of Computation
by
gunjanmimo
(
6
points)

2
views
#testseries
#gatebook
0
votes
0
answers
Self doubt for Moore Machine
Q – Construct a Moore machine that takes set of strings over {0,1} and produces A as output, if input ends with ‘10’ and produces B as output if it ends with ‘11’ else produces C. Is my Moore Machine correct ?
asked
May 12
in
Theory of Computation
by
Ananya2000
(
22
points)

18
views
0
votes
1
answer
self_doubt union of language in toc
What will be the union of L1 U L2 ? L1= {a^n b ^m  n≤m} L2={a^n b^m  n≥m}
answered
May 12
in
Theory of Computation
by
srestha
(
749
points)

27
views
regularlanguages
0
votes
1
answer
Self doubt from a video !
Is the above DFA correct for acceptiing a string that starts and ends with the same symbol ?
answered
May 9
in
Theory of Computation
by
Kushagra गुप्ता
(
415
points)

19
views
0
votes
0
answers
Self Doubt from a video
Is the following DFA correct for a accepting a string that starts and ends with the same symbol ?
asked
May 8
in
Theory of Computation
by
Ananya2000
(
22
points)

4
views
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 design 2 stack pda for language {wna=nb=nc where w belongs to (a,b,c)*}
asked
May 2
in
Theory of Computation
by
iamayush
(
6
points)

5
views
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
SELF DOUBT(TOCWhat type of language is this.)
if we have a language like: L={3,9,27,81,273….} what is this ? is this regular,CFL,CSL or recursive or recursively enumerable?
asked
Apr 29
in
Theory of Computation
by
Doraemon
(
115
points)

7
views
theoryofcomputation
+1
vote
1
answer
GATE2020CS51 Video Solution
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________
answered
Apr 28
in
Theory of Computation
by
amitkhurana512
(
187
points)

15
views
gate2020cs
numericalanswers
theoryofcomputation
videosolution
+1
vote
1
answer
GATE2020CS8 Video Solution
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ
answered
Apr 28
in
Theory of Computation
by
amitkhurana512
(
187
points)

6
views
gate2020cs
theoryofcomputation
videosolution
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
(
7
points)

9
views
theoryofcomputation
#toc
+1
vote
1
answer
GATE2020CS32 Video Solution
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ ...  free but not regular and $L_2$ is contextfree. Neither $L_1$ nor $L_2$ is context free. $L_1$ context free but $L_2$ is not contextfree.
answered
Apr 26
in
Theory of Computation
by
amitkhurana512
(
187
points)

14
views
gate2020cs
theoryofcomputation
videosolution
+1
vote
1
answer
GATE2020CS26 Video Solution
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
answered
Apr 26
in
Theory of Computation
by
amitkhurana512
(
187
points)

15
views
gate2020cs
theoryofcomputation
decidability
videosolution
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
Jul 2020
bittujash
6 Points
RavGopal
4 Points
ankeshsingh
2 Points
prakhar123
1 Points
arpit_18
1 Points
pravincesingh
1 Points
Shaik Masthan
1 Points
srestha
1 Points
sameer2009
1 Points
Recent questions and answers in Theory of Computation
7,525
questions
1,776
answers
10,835
comments
90,464
users