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
0
answers
1
Regular Languages
The solution to $X = r +Xs$ by Arden’s Lemma when s has ϵ a) an infinite number of solutions b) a finite number of solutions c) is always unique d) none
practicalmetal
asked
in
Theory of Computation
3 days
ago
by
practicalmetal
20
views
regular-language
theory-of-computation
finite-automata
0
votes
1
answer
2
Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }
himalay
answered
in
Theory of Computation
3 days
ago
by
himalay
55
views
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
1
answer
3
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
deathWalker
answered
in
Theory of Computation
6 days
ago
by
deathWalker
57
views
context-free-language
theory-of-computation
ace-test-series
0
votes
1
answer
4
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.
GNANESWARA SAI
answered
in
Theory of Computation
Mar 16
by
GNANESWARA SAI
85
views
context-free-language
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
4
answers
5
TOC
What are the number of states needed in minimal DFA, that accepts (1+1111)* A. 5 B. 4 C. 1 D. None
Bharat Bhushan
answered
in
Theory of Computation
Mar 10
by
Bharat Bhushan
2.9k
views
theory-of-computation
number-of-states
18
votes
3
answers
6
How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA
Bharat Bhushan
answered
in
Theory of Computation
Mar 5
by
Bharat Bhushan
81.1k
views
minimal-state-automata
theory-of-computation
finite-automata
combinatory
1
vote
2
answers
7
Peter Linz Edition 4 Exercise 3.1 Question 12 (Page No. 76)
Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.
Genius
answered
in
Theory of Computation
Mar 4
by
Genius
225
views
peter-linz
peter-linz-edition4
regular-expression
theory-of-computation
regular-language
0
votes
2
answers
8
context free grammar
what is the langauge generated by this grammar ? S-->aS | aSbS | ε what is the language
KG
answered
in
Theory of Computation
Mar 2
by
KG
80
views
theory-of-computation
context-free-language
context-free-grammar
8
votes
2
answers
9
GATE CSE 1988 | Question: 15
Consider the DFA $M$ and NFA $M_{2}$ as defined below. Let the language accepted by machine $M$ be $L$. What language machine $M_{2}$ accepts, if $F2=A?$ $F2=B?$ $F2=C?$ $F2=D?$ $M=(Q, \Sigma, \delta, q_0, F)$ $M_{2}=(Q2, \Sigma, \delta_2, q_{00}, F2)$ ... $D=\{\langle p, q, r \rangle \mid p,q \in Q; r \in F\}$
Genius
answered
in
Theory of Computation
Feb 26
by
Genius
1.6k
views
gate1988
descriptive
theory-of-computation
finite-automata
difficult
1
vote
1
answer
10
Peter Linz Edition 4 Exercise 3.1 Question 17 (Page No. 76)
Write regular expressions for the following languages on {$0, 1$}. (a) all strings ending in $01$, (b) all strings not ending in $01$, (c) all strings containing an even number of $0$'s, (d) Peter Linz Edition 4 ... (e) all strings with at most two occurrences of the substring $00$, (f) all strings not containing the substring $101$.
Harsh Saini_1
answered
in
Theory of Computation
Feb 25
by
Harsh Saini_1
368
views
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
2
votes
3
answers
11
Peter Linz Edition 4 Exercise 3.1 Question 16.d (Page No. 76)
Find a regular expression over Σ ={a,b,c} for all strings that contain no run of a's of length greater than 2. Here a run in a string is a sub string of length at least two as long as possible and consisting entirely of the same symbol. For eg, the string abbbaab contains a run of b's of length three and a tun of a's of length two.
Harsh Saini_1
answered
in
Theory of Computation
Feb 24
by
Harsh Saini_1
2.0k
views
theory-of-computation
peter-linz
peter-linz-edition4
regular-expression
1
vote
1
answer
12
Peter Linz Edition 4 Exercise 3.1 Question 15 (Page No. 76)
Find a regular expression for $L =$ {$w∈ $ {$0,1$}$^* : w$ has exactly one pair of consecutive zeros} .
Harsh Saini_1
answered
in
Theory of Computation
Feb 24
by
Harsh Saini_1
192
views
peter-linz
peter-linz-edition4
regular-expression
theory-of-computation
1
vote
1
answer
13
Peter Linz Edition 4 Exercise 3.1 Question 13 (Page No. 76)
Find a regular expression for $L =$ {$vwv: v, w ∈${$a, b$}$^*, |v| =2$}.
Harsh Saini_1
answered
in
Theory of Computation
Feb 23
by
Harsh Saini_1
143
views
peter-linz
peter-linz-edition4
regular-expression
theory-of-computation
regular-language
1
vote
1
answer
14
Peter Linz Edition 4 Exercise 3.1 Question 11 (Page No. 76)
Find a regular expression for $L =$ {$ab^nw: n ≥ 3, w ∈$ {$a, b$}$^+$}.
Harsh Saini_1
answered
in
Theory of Computation
Feb 23
by
Harsh Saini_1
153
views
peter-linz
peter-linz-edition4
regular-expression
theory-of-computation
2
votes
3
answers
15
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.
Hira Thakur
answered
in
Theory of Computation
Feb 16
by
Hira Thakur
993
views
gatecse-2023
theory-of-computation
identify-class-language
multiple-selects
1-mark
6
votes
2
answers
16
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)^{*}$
Hira Thakur
answered
in
Theory of Computation
Feb 16
by
Hira Thakur
1.3k
views
gatecse-2023
theory-of-computation
regular-expression
1-mark
0
votes
0
answers
17
Gate 2023
Consider the language L over the alphabet {0, 1}, given below: L = {w ∈ {0, 1}* | w does not contain three or more consecutive 1’s}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is ______ .
closed
ic3rror
asked
in
Theory of Computation
Feb 16
by
ic3rror
351
views
number-of-dfa
numerical-answers
3
votes
4
answers
18
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)
Hira Thakur
answered
in
Theory of Computation
Feb 16
by
Hira Thakur
1.1k
views
gatecse-2023
theory-of-computation
regular-expression
1-mark
2
votes
4
answers
19
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 ____________.
Hira Thakur
answered
in
Theory of Computation
Feb 16
by
Hira Thakur
977
views
gatecse-2023
theory-of-computation
minimal-state-automata
numerical-answers
2-marks
4
votes
2
answers
20
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
Deepak Poonia
answered
in
Theory of Computation
Feb 15
by
Deepak Poonia
999
views
gatecse-2023
theory-of-computation
context-free-grammar
2-marks
2
votes
2
answers
21
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\}$
Deepak Poonia
answered
in
Theory of Computation
Feb 15
by
Deepak Poonia
867
views
gatecse-2023
theory-of-computation
pushdown-automata
2-marks
0
votes
0
answers
22
#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
85
views
theory-of-computation
regular-language
context-free-language
0
votes
0
answers
23
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
101
views
theory-of-computation
peter-linz-edition5
turing-machine
0
votes
0
answers
24
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
182
views
theory-of-computation
descriptive
0
votes
0
answers
25
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
128
views
theory-of-computation
number-of-dfa
strings
0
votes
2
answers
26
Peter Linz Edition 4 Exercise 1.2 Question 12 (Page No. 28)
Give a simple description of the language generated by the grammar with productions $S \rightarrow aA,$ $A \rightarrow bS,$ $S \rightarrow λ.$
Hira Thakur
answered
in
Theory of Computation
Feb 6
by
Hira Thakur
255
views
peter-linz
peter-linz-edition4
theory-of-computation
grammar
0
votes
1
answer
27
Peter Linz Edition 4 Exercise 3.1 Question 26 (Page No. 77)
Find an nfa that accepts the language $L (aa^* (a + b))$.
Hira Thakur
answered
in
Theory of Computation
Feb 6
by
Hira Thakur
172
views
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
finite-automata
0
votes
1
answer
28
Peter Linz Edition 4 Exercise 3.2 Question 1 (Page No. 87)
Find an nfa that accepts the language $L (ab^*aa + bba^*ab)$.
Hira Thakur
answered
in
Theory of Computation
Feb 6
by
Hira Thakur
96
views
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
1
vote
2
answers
29
Peter Linz Edition 4 Exercise 3.1 Question 1 (Page No. 75)
Find all strings in $L((a + b) b (a + ab)^*)$ of length less than four.
Hira Thakur
answered
in
Theory of Computation
Feb 6
by
Hira Thakur
378
views
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
0
votes
0
answers
30
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) ∗ ).
closed
Silver_Reaper
asked
in
Theory of Computation
Feb 6
by
Silver_Reaper
129
views
theory-of-computation
regular-language
grammar
peter-linz
1
vote
2
answers
31
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)^*$
closed
Hira Thakur
answered
in
Theory of Computation
Feb 6
by
Hira Thakur
440
views
memorybased-gatecse2023
goclasses
theory-of-computation
regular-expression
2
votes
0
answers
32
Can DCFL be ambiguous?
Can DCFL be ambiguous?
h4kr
asked
in
Theory of Computation
Feb 2
by
h4kr
137
views
theory-of-computation
dcfl
ambiguous
0
votes
3
answers
33
For any language, if the union of both is regular, then are those languages regular languages as well?
abhinowKatore
answered
in
Theory of Computation
Feb 1
by
abhinowKatore
470
views
finite-automata
0
votes
1
answer
34
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.
Pranavpurkar
answered
in
Theory of Computation
Jan 30
by
Pranavpurkar
129
views
theory-of-computation
peter-linz
finite-automata
0
votes
1
answer
35
#gate questions
which one true 1. Determining whether context-free grammar is un-decidable 2. Whether a given grammar is context-free is decidable
elsar martin
answered
in
Theory of Computation
Jan 30
by
elsar martin
96
views
decidability
0
votes
2
answers
36
TOC | Made Easy mock
Vijay_Ram
answered
in
Theory of Computation
Jan 28
by
Vijay_Ram
142
views
made-easy-test-series
theory-of-computation
numerical-answers
test-series
0
votes
0
answers
37
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
81
views
theory-of-computation
peter-linz
finite-automata
0
votes
1
answer
38
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
94
views
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
0
answers
39
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
92
views
multiple-selects
regular-language
theory-of-computation
made-easy-test-series
0
votes
0
answers
40
derive a language from a grammar
{M ∈ {a,b}∗ | M contains at least three bs} {N ∈ {a,b}∗ | N has an odd length and a is in the middle always}
moe12leb
asked
in
Theory of Computation
Jan 21
by
moe12leb
64
views
theory-of-computation
regular-language
context-free-grammar
To see more, click for all the
questions in this category
.
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
Central Pollution Control Board CPCB Various Post Recruitment 2023
MP Rajya Sahkari Apex Bank Various Post Recruitment 2023
NITIE MUMBAI throgh GATE
PGCIL recruitment 2023 – Apply Online For 138 Posts through GATE
Admission guidance for GATE CSE 2023
Subjects
All categories
General Aptitude
(2.6k)
Engineering Mathematics
(9.4k)
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
(655)
Exam Queries
(847)
Tier 1 Placement Questions
(17)
Job Queries
(77)
Projects
(9)
Unknown Category
(866)
Recent questions and answers in Theory of Computation
Recent Blog Comments
Please see the updated link.
Unfortunately there won't be a hardcopy coming...
this book is not available on amazon now, i want...
Yes
Hi! @AnkitMazumder14 bhaiya,Is python...