Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions and answers in Theory of Computation
0
votes
1
answer
1
Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.
Mrityudoot
answered
in
Theory of Computation
2 days
ago
by
Mrityudoot
36
views
0
votes
0
answers
2
Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non-Recursively ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?
dopq12
asked
in
Theory of Computation
Mar 5
by
dopq12
58
views
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
2
votes
3
answers
3
GATE CSE 2024 | Set 1 | Question: 51
Consider the following two regular expressions over the alphabet $\{0,1\}$ : $r= 0^{*}+1^{*}$ $s = 01^{*} + 10^{*}$ The total number of strings of length less than or equal to $5$, which are neither in $r$ nor in $s$, is ________.
jvishal
answered
in
Theory of Computation
Mar 3
by
jvishal
1.4k
views
gatecse2024-set1
numerical-answers
theory-of-computation
0
votes
2
answers
4
#Convert the NFA in to equivalent R.E.
m1_lan____
answered
in
Theory of Computation
Feb 26
by
m1_lan____
117
views
theory-of-computation
finite-automata
0
votes
0
answers
5
#toc
Çșȇ ʛấẗẻ
asked
in
Theory of Computation
Feb 24
by
Çșȇ ʛấẗẻ
65
views
theory-of-computation
finite-automata
regular-expression
regular-language
context-free-language
0
votes
0
answers
6
Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR,∑,δR,q0R,FR).
Vedantthakkar
asked
in
Theory of Computation
Feb 24
by
Vedantthakkar
98
views
0
votes
0
answers
7
Pumping Lemma
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and explain why pumping it leads to a contradiction. {aaabnan∣n≥0} {ww∣w∈Σ∗}
jg662
asked
in
Theory of Computation
Feb 23
by
jg662
57
views
theory-of-computation
pumping-lemma
2
votes
1
answer
8
GATE CSE 2024 | Set 2 | Question: 42
Consider a context-free grammar $\text{G}$ with the following $3$ rules. \[ S \rightarrow a S, S \rightarrow a S b S , S \rightarrow c \] Let $w \in L(G)$. Let $ n_{a}(w), n_{b}(w), n_{c}(w) $ denote the number of times $a, b, c$ occur in $w$, respectively. Which of ... $n_{a}(w)>n_{c}(w)-2$ $n_{c}(w)=n_{b}(w)+1$ $n_{c}(w)=n_{b}(w) * 2$
liontig37
answered
in
Theory of Computation
Feb 23
by
liontig37
1.5k
views
gatecse2024-set2
theory-of-computation
multiple-selects
0
votes
0
answers
9
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement. a. {0"1"0"| m, n 2 0} b. (0"1"| m ‡ n) c. (w| w € {0,1)* is not a palindrome) d. (wtw| w,t € (0,1)*)
krishan_rathi
asked
in
Theory of Computation
Feb 22
by
krishan_rathi
95
views
theory-of-computation
0
votes
1
answer
10
GATE CSE 2024 | Set 1 | Question: 40
Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. Which ... $4$ are distinguishable in $M$ States $2$ and $5$ are distinguishable in $M$ Any string $w$ with $n_0(w)=n_1(w)$ is in $L(M)$
phaniphani
answered
in
Theory of Computation
Feb 17
by
phaniphani
2.1k
views
gatecse2024-set1
multiple-selects
theory-of-computation
0
votes
1
answer
11
GATE CSE 2024 | Set 1 | Question: 13
Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE? $L_1=L_2$ if and only if $L_1 \cap \overline{L_2}=\phi$ $L_1 \cup L_3$ is not regular $\overline{L_3}$ is not regular $\overline{L_1} \cup \overline{L_2}$ is regular
malaviya_parth
answered
in
Theory of Computation
Feb 17
by
malaviya_parth
2.4k
views
gatecse2024-set1
multiple-selects
theory-of-computation
1
vote
1
answer
12
GATE CSE 2024 | Set 2 | Question: 31
Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$? $(00)^{*}+1(11)^{*}$ $0^{*}+\left(1+0(00)^{*}\right)(11)^{*}$ $(00)^{*}+\left(1+(00)^{*}\right)(11)^{*}$ $0^{+}+1(11)^{*}+0(11)^{*}$
Deepak Poonia
answered
in
Theory of Computation
Feb 17
by
Deepak Poonia
1.9k
views
gatecse2024-set2
theory-of-computation
1
vote
2
answers
13
GATE CSE 2024 | Set 2 | Question: 52
Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.
DEBANJAN DAS2k
answered
in
Theory of Computation
Feb 17
by
DEBANJAN DAS2k
1.6k
views
gatecse2024-set2
numerical-answers
theory-of-computation
2
votes
2
answers
14
GATE CSE 2024 | Set 2 | Question: 12
Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below? $0^{*} 1\left(0+10^{*} 1\right)^{*}$ $0^{*}\left(10^{*} 11\right)^{*} 0^{*}$ $0^{*} 1\left(010^{*} 1\right)^{*} 0^{*}$ $0\left(1+0^{*} 10^{*} 1\right)^{*} 0^{*}$
Deepak Poonia
answered
in
Theory of Computation
Feb 17
by
Deepak Poonia
2.1k
views
gatecse2024-set2
theory-of-computation
0
votes
1
answer
15
Not Regular language [find out]
Why is C is regular as it non regular as? Please help me with this confusion
bluesta
answered
in
Theory of Computation
Feb 15
by
bluesta
189
views
finite-automata
theory-of-computation
regular-language
0
votes
1
answer
16
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.{w| w starts with 0 and has odd length, or starts with 1 and has even length}
Sujith48
answered
in
Theory of Computation
Feb 15
by
Sujith48
88
views
0
votes
0
answers
17
Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}.{w| w does not contain the substring ab} {w| w does not contain the substring baba} {w| w contains neither the substrings ab nor ba} {w| w is any string not in a∗ ∪ b∗ } ( ∪ is the union )
rania
asked
in
Theory of Computation
Feb 14
by
rania
86
views
0
votes
3
answers
18
michael sipser chp 1, 3rd edition, Q 12 , dfa
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab } give a DFA with Five states that recognizes D and a regular expression that generates D.
cherry348
answered
in
Theory of Computation
Feb 13
by
cherry348
3.5k
views
theory-of-computation
finite-automata
3
votes
1
answer
19
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 32
Which of the following sets has the greatest cardinality? The set of real numbers R The set of all functions from R to {0,1} The set of all finite subsets of natural numbers The set of all finite-length binary strings
Bharadwaja1557
answered
in
Theory of Computation
Feb 7
by
Bharadwaja1557
391
views
goclasses2024-mockgate-14
theory-of-computation
finite-automata
1-mark
5
votes
1
answer
20
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 64
Which of the following languages are Turing-recognizable? A. $\{\langle M\rangle \mid M$ is a (deterministic) Turing machine and $M$ accepts 010$\}$. B. $\{\langle M\rangle \mid M$ is a nondeterministic Turing machine and $M$ accepts 010 ... $\left\{\langle M\rangle \mid M\right.$ is a Turing machine and $\left.L(M)=\Sigma^*\right\}$.
Prabhas
answered
in
Theory of Computation
Feb 6
by
Prabhas
414
views
goclasses2024-mockgate-14
theory-of-computation
turing-machine
multiple-selects
2-marks
3
votes
1
answer
21
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 35
Which of the following strings are a member of the language described by the regular expression $\left(a^* {b} {a}^* b a^* b {a}^*\right)^*$ $b b b b$ $bbaaabb$ $bbaaabbbabb$ $b b a b b b a b$
shubhsy1729
answered
in
Theory of Computation
Feb 6
by
shubhsy1729
480
views
goclasses2024-mockgate-14
theory-of-computation
regular-expression
multiple-selects
1-mark
4
votes
0
answers
22
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 31
DeMorgan's Laws ensure that Closure under intersection and complementation imply closure under union. Closure under intersection and union imply closure under complementation. Closure under union and complementation imply closure ... Closure under any two of union, intersection, and complementation implies closure under all three.
GO Classes
asked
in
Theory of Computation
Feb 5
by
GO Classes
299
views
goclasses2024-mockgate-14
theory-of-computation
closure-property
multiple-selects
1-mark
4
votes
0
answers
23
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 65
Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$ $L^{\star}$ is infinite. $L$ is accepted by some DFA if and only if $L$ is accepted by some NFA. If $\mathrm{L}$ is the ... $\mathrm{L}$ is undecidable. If $\mathrm{L}$ is the union of two decidable languages, then $\mathrm{L}$ is decidable.
GO Classes
asked
in
Theory of Computation
Feb 5
by
GO Classes
548
views
goclasses2024-mockgate-14
theory-of-computation
decidability
multiple-selects
2-marks
53
votes
3
answers
24
GATE CSE 2006 | Question: 30
For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$Which ... following statements is true? $L$ is recursively enumerable, but not recursive $L$ is recursive, but not context-free $L$ is context-free, but not regular $L$ is regular
Amoljadhav
answered
in
Theory of Computation
Feb 4
by
Amoljadhav
7.5k
views
gatecse-2006
theory-of-computation
normal
identify-class-language
0
votes
1
answer
25
Why is L1 not DCFL?
Mrityudoot
answered
in
Theory of Computation
Jan 28
by
Mrityudoot
98
views
theory-of-computation
made-easy-test-series
6
votes
1
answer
26
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 23
Which of the following statements is/are false? If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ is not ambiguous. For every number $n$, the language $\text{L}_n=\left\{0^n 1^n\right\}$ is ... 's a $10$-state NFA that accepts $\text{L}$ then there's a $100$-state DFA that accepts $\mathrm{L}$.
GO Classes
answered
in
Theory of Computation
Jan 28
by
GO Classes
567
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
context-free-language
multiple-selects
1-mark
5
votes
1
answer
27
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 24
Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then the maximum possible cardinality of $\text{L(M)}$ is __________.
GO Classes
answered
in
Theory of Computation
Jan 28
by
GO Classes
497
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
finite-automata
1-mark
5
votes
1
answer
28
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55
Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$. Which of the following sets is not recursively enumerable ... machine halts on the input $m$. The set of $n$ such that all Turing machines halt on the input $n$.
GO Classes
answered
in
Theory of Computation
Jan 28
by
GO Classes
427
views
goclasses2024-mockgate-13
goclasses
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
2-marks
7
votes
1
answer
29
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 56
For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual power of strings) and $x^{\downarrow m}=x_1^m \cdots x_n^m$. For empty ... $\left\{(a b c)^{\downarrow n} \mid n \geq 0\right\}$
GO Classes
answered
in
Theory of Computation
Jan 28
by
GO Classes
424
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
context-free-language
multiple-selects
2-marks
8
votes
1
answer
30
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 57
Consider a pushdown automaton (PDA) with two control states $Q=\{q 1, q 2\}$, start state $q 1$, input alphabet $\Sigma=\{a, b\}$, stack alphabet $\Gamma=\{\perp, a\}$ (where $\perp$ is the start symbol ... $21$ accepted by the above pushdown automaton is _________.
GO Classes
answered
in
Theory of Computation
Jan 28
by
GO Classes
518
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
pushdown-automata
2-marks
21
votes
5
answers
31
GATE CSE 2001 | Question: 2.6
Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ ... $L1$ and $L2$ Only $L2, L3$ and $L4$ Only $L3$ and $L4$ Only $L3$
bluesta
answered
in
Theory of Computation
Jan 28
by
bluesta
7.9k
views
gatecse-2001
theory-of-computation
normal
regular-language
1
vote
1
answer
32
Gate CSE Made Easy Test Series
Construct a minimal finite state automation that accepts the language over {0, 1} of all strings that contain neither the substring 00 nor the substring 11. What is the number of states in this machine? For this question when we draw the DFA there ... and NFA contains 3 states minimum. So according to question what shall be the answer for this question? 3 or 4? Why?
prasantkr.singh
answered
in
Theory of Computation
Jan 23
by
prasantkr.singh
194
views
theory-of-computation
made-easy-test-series
1
vote
1
answer
33
Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?
yadavmayank742
answered
in
Theory of Computation
Jan 22
by
yadavmayank742
128
views
theory-of-computation
context-free-language
dcfl
identify-class-language
pushdown-automata
3
votes
2
answers
34
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 44
Which of the following statements is/are false? Let $\text{A}$ and $\text{B}$ be sets of languages over some fixed alphabet $\Sigma$, with $\text{A} \subseteq \text{B}$. If $\text{A}$ is closed under some operation $\text{P},$ then ... $\mathrm{L} 2$ $\subseteq \mathrm{L} 1$, then $\mathrm{L} 2$ is decidable.)
raj_uddeshya157
answered
in
Theory of Computation
Jan 21
by
raj_uddeshya157
502
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
identify-class-language
multiple-selects
2-marks
32
votes
3
answers
35
GATE CSE 2001 | Question: 7
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
ajayraho
answered
in
Theory of Computation
Jan 21
by
ajayraho
4.5k
views
gatecse-2001
theory-of-computation
decidability
turing-machine
easy
descriptive
3
votes
1
answer
36
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 15
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$. $\emptyset$ $\{a\}^*$ $\{a\}$ $\{\varepsilon\}$
GO Classes
answered
in
Theory of Computation
Jan 21
by
GO Classes
416
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
1-mark
easy
2
votes
1
answer
37
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 42
Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensures that $L_1 \cap L_2$ ... and $\left.m \geq 0\right\}$ $L_2=\left\{a^k b^{2 k} c^{2 k} \mid k \geq 0\right\}$
GO Classes
answered
in
Theory of Computation
Jan 21
by
GO Classes
472
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
context-free-language
multiple-selects
2-marks
8
votes
1
answer
38
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true? If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite ... $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite.
GO Classes
answered
in
Theory of Computation
Jan 21
by
GO Classes
593
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
multiple-selects
2-marks
47
votes
4
answers
39
GATE IT 2007 | Question: 71
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which of the following non-deterministic finite automata recognizes the language defined by the regular expression $R$? Edges labeled $\lambda $ denote transitions on the empty string.
bluesta
answered
in
Theory of Computation
Jan 20
by
bluesta
8.1k
views
gateit-2007
theory-of-computation
finite-automata
normal
0
votes
1
answer
40
Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?
ByteCode
answered
in
Theory of Computation
Jan 19
by
ByteCode
367
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
gnf
To see more, click for all the
questions in this category
.
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(24)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(682)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
243k
comments
79.7k
users
Recent questions and answers in Theory of Computation
Recent Blog Comments
Hlo I'm Rupesh I got AIR 3485 in gate CS and AIR...
@Ajay Sasank here is the direct link...
Thank you for the post didi My GATE 2023 & 2024...
I Hope it helps 😊
Today's best post I seen thank you for motivation