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
1
vote
3
answers
1
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 _________.
Mihir L. Agrawal
answered
in
Theory of Computation
Mar 23
by
Mihir L. Agrawal
1.7k
views
gatecse2024-set2
numerical-answers
theory-of-computation
0
votes
0
answers
2
THEORY OF AUTOMATA ASSIGNMENT # 1 1. Write regular expressions and draw NFA for the following languages over the alphabet Σ = {a, b}: a. All strings that do not end with aa. b. All strings that contain an even number of b’s c. All strings that contain atleast two a’s or exactly two b’s d. All strings that ends with double letters (aa or bb) e. All strings that does not ends with double letter.(can end with ab or ba)
Talha Riaz
asked
in
Theory of Computation
Mar 23
by
Talha Riaz
24
views
0
votes
1
answer
3
Set of binary strings starting with 11 and ending with 00. E.g., 1100,1110100 ,1100100
prasantkr.singh
answered
in
Theory of Computation
Mar 22
by
prasantkr.singh
42
views
1
vote
2
answers
4
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)^{*}$
ashwinsuthar1
answered
in
Theory of Computation
Mar 19
by
ashwinsuthar1
2.0k
views
gatecse2024-set2
theory-of-computation
0
votes
1
answer
5
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
Mar 16
by
Mrityudoot
64
views
0
votes
0
answers
6
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- ... 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
75
views
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
2
votes
3
answers
7
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 2
by
jvishal
1.5k
views
gatecse2024-set1
numerical-answers
theory-of-computation
0
votes
2
answers
8
#Convert the NFA in to equivalent R.E.
m1_lan____
answered
in
Theory of Computation
Feb 26
by
m1_lan____
142
views
theory-of-computation
finite-automata
0
votes
0
answers
9
#toc
Çșȇ ʛấẗẻ
asked
in
Theory of Computation
Feb 24
by
Çșȇ ʛấẗẻ
80
views
theory-of-computation
finite-automata
regular-expression
regular-language
context-free-language
0
votes
0
answers
10
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
118
views
0
votes
0
answers
11
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 22
by
jg662
71
views
theory-of-computation
pumping-lemma
2
votes
1
answer
12
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 22
by
liontig37
1.6k
views
gatecse2024-set2
theory-of-computation
multiple-selects
0
votes
0
answers
13
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 21
by
krishan_rathi
111
views
theory-of-computation
0
votes
1
answer
14
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$. ... $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 16
by
phaniphani
2.2k
views
gatecse2024-set1
multiple-selects
theory-of-computation
0
votes
1
answer
15
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 16
by
malaviya_parth
2.5k
views
gatecse2024-set1
multiple-selects
theory-of-computation
2
votes
2
answers
16
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 16
by
Deepak Poonia
2.2k
views
gatecse2024-set2
theory-of-computation
0
votes
1
answer
17
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
214
views
finite-automata
theory-of-computation
regular-language
0
votes
1
answer
18
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
101
views
0
votes
0
answers
19
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
105
views
0
votes
3
answers
20
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 12
by
cherry348
3.6k
views
theory-of-computation
finite-automata
3
votes
1
answer
21
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
404
views
goclasses2024-mockgate-14
theory-of-computation
finite-automata
1-mark
5
votes
1
answer
22
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
443
views
goclasses2024-mockgate-14
theory-of-computation
turing-machine
multiple-selects
2-marks
3
votes
1
answer
23
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
523
views
goclasses2024-mockgate-14
theory-of-computation
regular-expression
multiple-selects
1-mark
4
votes
0
answers
24
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
306
views
goclasses2024-mockgate-14
theory-of-computation
closure-property
multiple-selects
1-mark
4
votes
0
answers
25
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
575
views
goclasses2024-mockgate-14
theory-of-computation
decidability
multiple-selects
2-marks
53
votes
3
answers
26
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 3
by
Amoljadhav
7.6k
views
gatecse-2006
theory-of-computation
normal
identify-class-language
0
votes
1
answer
27
Why is L1 not DCFL?
Mrityudoot
answered
in
Theory of Computation
Jan 28
by
Mrityudoot
113
views
theory-of-computation
made-easy-test-series
6
votes
1
answer
28
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$ ... 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
601
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
context-free-language
multiple-selects
1-mark
5
votes
1
answer
29
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
521
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
finite-automata
1-mark
5
votes
1
answer
30
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 ... 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
470
views
goclasses2024-mockgate-13
goclasses
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
2-marks
7
votes
1
answer
31
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
449
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
context-free-language
multiple-selects
2-marks
8
votes
1
answer
32
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
542
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
pushdown-automata
2-marks
21
votes
5
answers
33
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
8.0k
views
gatecse-2001
theory-of-computation
normal
regular-language
1
vote
1
answer
34
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
223
views
theory-of-computation
made-easy-test-series
1
vote
1
answer
35
Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?
yadavmayank742
answered
in
Theory of Computation
Jan 21
by
yadavmayank742
144
views
theory-of-computation
context-free-language
dcfl
identify-class-language
pushdown-automata
3
votes
2
answers
36
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
536
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
identify-class-language
multiple-selects
2-marks
32
votes
3
answers
37
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.6k
views
gatecse-2001
theory-of-computation
decidability
turing-machine
easy
descriptive
3
votes
1
answer
38
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
438
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
1-mark
easy
2
votes
1
answer
39
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
503
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
context-free-language
multiple-selects
2-marks
8
votes
1
answer
40
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
640
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
multiple-selects
2-marks
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
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions and answers in Theory of Computation
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...