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
Webpage for Theory of Computation:
Recent questions tagged theory-of-computation
0
votes
1
answer
1
Prove that n! = Ω(n^100)
wtquevb123
asked
in
Algorithms
Mar 14
by
wtquevb123
53
views
theory-of-computation
algorithms
time-complexity
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- ... 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
66
views
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
0
votes
0
answers
3
#toc
Çșȇ ʛấẗẻ
asked
in
Theory of Computation
Feb 24
by
Çșȇ ʛấẗẻ
72
views
theory-of-computation
finite-automata
regular-expression
regular-language
context-free-language
0
votes
2
answers
4
#Convert the NFA in to equivalent R.E.
Çșȇ ʛấẗẻ
asked
in
Theory of Computation
Feb 24
by
Çșȇ ʛấẗẻ
129
views
theory-of-computation
finite-automata
0
votes
0
answers
5
#TOC
Çșȇ ʛấẗẻ
asked
in
Databases
Feb 24
by
Çșȇ ʛấẗẻ
45
views
theory-of-computation
finite-automata
regular-expression
regular-language
0
votes
0
answers
6
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
66
views
theory-of-computation
pumping-lemma
0
votes
0
answers
7
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
106
views
theory-of-computation
2
votes
2
answers
8
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^{*}$
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
2.1k
views
gatecse2024-set2
theory-of-computation
1
vote
2
answers
9
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)^{*}$
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
2.0k
views
gatecse2024-set2
theory-of-computation
2
votes
1
answer
10
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$
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
1.6k
views
gatecse2024-set2
theory-of-computation
multiple-selects
1
vote
3
answers
11
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 _________.
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
1.7k
views
gatecse2024-set2
numerical-answers
theory-of-computation
0
votes
1
answer
12
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
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
2.4k
views
gatecse2024-set1
multiple-selects
theory-of-computation
0
votes
1
answer
13
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)$
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
2.2k
views
gatecse2024-set1
multiple-selects
theory-of-computation
2
votes
3
answers
14
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 ________.
Arjun
asked
in
Theory of Computation
Feb 16
by
Arjun
1.5k
views
gatecse2024-set1
numerical-answers
theory-of-computation
0
votes
0
answers
15
Regular expression to finite automata
Çșȇ ʛấẗẻ
asked
in
Mathematical Logic
Feb 15
by
Çșȇ ʛấẗẻ
195
views
finite-automata
theory-of-computation
regular-expression
4
votes
0
answers
16
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
301
views
goclasses2024-mockgate-14
theory-of-computation
closure-property
multiple-selects
1-mark
3
votes
1
answer
17
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
GO Classes
asked
in
Theory of Computation
Feb 5
by
GO Classes
397
views
goclasses2024-mockgate-14
theory-of-computation
finite-automata
1-mark
3
votes
1
answer
18
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$
GO Classes
asked
in
Theory of Computation
Feb 5
by
GO Classes
489
views
goclasses2024-mockgate-14
theory-of-computation
regular-expression
multiple-selects
1-mark
5
votes
1
answer
19
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\}$.
GO Classes
asked
in
Theory of Computation
Feb 5
by
GO Classes
424
views
goclasses2024-mockgate-14
theory-of-computation
turing-machine
multiple-selects
2-marks
4
votes
0
answers
20
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
552
views
goclasses2024-mockgate-14
theory-of-computation
decidability
multiple-selects
2-marks
6
votes
1
answer
21
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
asked
in
Theory of Computation
Jan 28
by
GO Classes
577
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
context-free-language
multiple-selects
1-mark
5
votes
1
answer
22
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
asked
in
Theory of Computation
Jan 28
by
GO Classes
511
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
finite-automata
1-mark
5
votes
1
answer
23
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
asked
in
Theory of Computation
Jan 28
by
GO Classes
433
views
goclasses2024-mockgate-13
goclasses
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
2-marks
7
votes
1
answer
24
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
asked
in
Theory of Computation
Jan 28
by
GO Classes
430
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
context-free-language
multiple-selects
2-marks
8
votes
1
answer
25
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
asked
in
Theory of Computation
Jan 28
by
GO Classes
524
views
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
pushdown-automata
2-marks
0
votes
1
answer
26
Why is L1 not DCFL?
pcla
asked
in
Theory of Computation
Jan 27
by
pcla
100
views
theory-of-computation
made-easy-test-series
1
vote
1
answer
27
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?
abhiyodayapandey
asked
in
Theory of Computation
Jan 21
by
abhiyodayapandey
204
views
theory-of-computation
made-easy-test-series
3
votes
1
answer
28
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
asked
in
Theory of Computation
Jan 21
by
GO Classes
424
views
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
1-mark
easy
Page:
1
2
3
4
5
6
...
155
next »
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 tagged 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:...