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
0
answers
1
Context Free Language
The complement of the languages: i) {ww | w in (0+1)*} ii) {$a^n b^nc^n$ | n>1} are a) Context Free b) Not Context Free c)are DCFL’s d)None
practicalmetal
asked
in
Theory of Computation
1 hour
ago
by
practicalmetal
6
views
context-free-language
theory-of-computation
ace-test-series
0
votes
0
answers
2
Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }
practicalmetal
asked
in
Theory of Computation
1 hour
ago
by
practicalmetal
6
views
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
1
answer
3
Context Free Languages
Is the following language context free: The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.
practicalmetal
asked
in
Theory of Computation
5 days
ago
by
practicalmetal
65
views
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
6
votes
2
answers
4
GATE CSE 2023 | Question: 4
Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state. Which one of the following ... $1\left(0^{*} 11\right)^{*}$ $0(0+1)^{*}$ $1(0+11)^{*}$ $1\left(110^{*}\right)^{*}$
admin
asked
in
Theory of Computation
Feb 15
by
admin
1.2k
views
gatecse-2023
theory-of-computation
regular-expression
1-mark
3
votes
4
answers
5
GATE CSE 2023 | Question: 9
Consider the following definition of a lexical token $\textbf{id}$ for an identifier in a programming language, using extended regular expressions: \[ \begin{array}{ll} \textbf{ letter } & \rightarrow[\mathrm{A}-\mathrm{Za}-\mathrm{ ... Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)
admin
asked
in
Theory of Computation
Feb 15
by
admin
1.0k
views
gatecse-2023
theory-of-computation
regular-expression
1-mark
2
votes
3
answers
6
GATE CSE 2023 | Question: 14
Which of the following statements is/are $\text{CORRECT}?$ The intersection of two regular languages is regular. The intersection of two context-free languages is context-free. The intersection of two recursive languages is recursive. The intersection of two recursively enumerable languages is recursively enumerable.
admin
asked
in
Theory of Computation
Feb 15
by
admin
932
views
gatecse-2023
theory-of-computation
identify-class-language
multiple-selects
1-mark
4
votes
2
answers
7
GATE CSE 2023 | Question: 29
Consider the context-free grammar $G$ below \[ \begin{array}{l} S \rightarrow a S b \mid X \\ X \rightarrow a X \mid X b \mid a \mid b, \end{array} \] where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non- ... $G$ is $a^{\ast} b^{\ast}(a+b)$ The language generated by $G$ is not a regular language
admin
asked
in
Theory of Computation
Feb 15
by
admin
928
views
gatecse-2023
theory-of-computation
context-free-grammar
2-marks
2
votes
2
answers
8
GATE CSE 2023 | Question: 30
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ ... $\left.0 \leq n\right\}$ $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$
admin
asked
in
Theory of Computation
Feb 15
by
admin
822
views
gatecse-2023
theory-of-computation
pushdown-automata
2-marks
2
votes
4
answers
9
GATE CSE 2023 | Question: 53
Consider the language $L$ over the alphabet $\{0,1\}$, given below: \[ L=\left\{w \in\{0,1\}^{*} \mid w \text { does not contain three or more consecutive } 1 \text { 's }\right\} . \] The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.
admin
asked
in
Theory of Computation
Feb 15
by
admin
913
views
gatecse-2023
theory-of-computation
minimal-state-automata
numerical-answers
2-marks
0
votes
0
answers
10
#TIFR
Consider the language $L = \{a^i \$ a^j \$ b^k \$ | k ⩽ max(i, j), i, j, k ≥ 0\}$ over the alphabet $\sum = \{a, b, \$ \}$. The complement of the language L, that is, $\sum^* - \text{ L}$ is denoted by $L'$. Which of the following is ... d) $L$ is a context-free language and $L'$ is not a context-free language. (e) Neither is $L$ a context-free language nor is $L'$ a context-free language.
amit166
asked
in
Theory of Computation
Feb 13
by
amit166
82
views
theory-of-computation
regular-language
context-free-language
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 10.5 Question 3
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.
borhanElmi
asked
in
Theory of Computation
Feb 9
by
borhanElmi
99
views
theory-of-computation
peter-linz-edition5
turing-machine
0
votes
0
answers
12
Isi Kolkata 2022
Prove or disprove the following statements: (i) L1 = {0^i1^j | i, j ∈ N} is a regular language. (ii) L2 = {0^n1^n | n ∈ N} is a regular language. (iii) For x ∈ {0, 1}*, R(x) denotes the string obtained by reversing the string x. C(x) denotes the string ... 0 in the string x. L3 = {x ∈ {0, 1}* | x = R (C (x))} is a regular language. How to solve this in subjective way..
devilstephen7
asked
in
Theory of Computation
Feb 8
by
devilstephen7
178
views
theory-of-computation
descriptive
0
votes
0
answers
13
Computational Theory
Give the state diagram of DFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0, 1}. {w | accept all string except 11 or 110} {w | w begins with a 11 and ends with a 0} {w | All string accepted except ... w | w contains at least three 0s } { w | w contains the substring 0101, i.e., w = x0101y for some x and y }
ahmed5
asked
in
Theory of Computation
Feb 8
by
ahmed5
123
views
theory-of-computation
number-of-dfa
strings
0
votes
0
answers
14
An Introduction to Formal Languages and Automata,Peter Linz,6th edition,exercise 3.3 q3
Find a regular grammar that generates the language L (aa ∗ (ab + a) ∗ ).
Silver_Reaper
asked
in
Theory of Computation
Feb 6
by
Silver_Reaper
122
views
theory-of-computation
regular-language
grammar
peter-linz
1
vote
2
answers
15
GATE CSE 2023 | Memory Based Question: 25
Consider the following finite automata and find the correct regular expression. $0(0+11)^*$ $1(0+11)^*$ $1(0 * 11)^*$ $0\left(0^* 11\right)^*$
GO Classes
asked
in
Theory of Computation
Feb 6
by
GO Classes
427
views
memorybased-gatecse2023
goclasses
theory-of-computation
regular-expression
2
votes
0
answers
16
Can DCFL be ambiguous?
Can DCFL be ambiguous?
h4kr
asked
in
Theory of Computation
Feb 2
by
h4kr
134
views
theory-of-computation
dcfl
ambiguous
0
votes
1
answer
17
An Introduction to Formal Languages and Automata,6th edition,Exercise 2.3 Q2.
Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.
Silver_Reaper
asked
in
Theory of Computation
Jan 28
by
Silver_Reaper
111
views
theory-of-computation
peter-linz
finite-automata
0
votes
2
answers
18
TOC | Made Easy mock
abhinowKatore
asked
in
Theory of Computation
Jan 24
by
abhinowKatore
138
views
made-easy-test-series
theory-of-computation
numerical-answers
test-series
0
votes
0
answers
19
An Introduction to Formal Languages and Automata Peter Linz 6th Edition.Exercise 2.1 4 d,e
For Σ = {a, b}, construct dfa’s that accept the sets consisting of: (d) all strings with at least one b and exactly two a’s. (e) all the strings with exactly two a’s and more than three b’s.
Silver_Reaper
asked
in
Theory of Computation
Jan 24
by
Silver_Reaper
74
views
theory-of-computation
peter-linz
finite-automata
0
votes
1
answer
20
Self Doubt
Consider L is recursive language and G is Recursively Enumerable then, L' union G is Recursively enumerable. Can someone please explain me this statement why it is true.?
TusharKumar
asked
in
Theory of Computation
Jan 21
by
TusharKumar
90
views
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
0
answers
21
Made Easy Gate Mock -1
Let L be a language over {a,b} that contains the same number of occurrences of a and b. which of the following is non-regular? a. b. c. d. MSQ & answer is a,c,d
TusharKumar
asked
in
Theory of Computation
Jan 21
by
TusharKumar
84
views
multiple-selects
regular-language
theory-of-computation
made-easy-test-series
Page:
1
2
3
4
5
6
...
148
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
My journey from being a MSc student to AIR 239 in GATE CSE 2023 and qualified UGC-NET JRF.
NEEPCO Recruitment 2023
GATE CSE 2023 Results
IIIT Banglore MTech 2023-24
IIIT-Delhi MTech 2023-24
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.3k)
Others
(2.5k)
Admissions
(653)
Exam Queries
(844)
Tier 1 Placement Questions
(17)
Job Queries
(76)
Projects
(9)
Unknown Category
(866)
Recent questions tagged theory-of-computation
Recent Blog Comments
congrats pranab
Congratulations @Pranab Paul 10 🥳
sir give access to these tests at least mid May...
Was there interview for mtech as well?
Check CCMT website for previous year cutoff for...