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
2
answers
1
Regular expression
is a(ba)*=(ab)*a?
kumar123
answered
in
Theory of Computation
5 days
ago
by
kumar123
80
views
theory-of-computation
regular-expression
finite-automata
0
votes
1
answer
2
Peter Linz Edition 5 Exercise 12.1 Question 9 (Page No. 308)
$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ ... that is, given a pda as in Definition, can we always predict whether or not the automaton will halt on input $w?$
iselfraja
answered
in
Theory of Computation
6 days
ago
by
iselfraja
157
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
1
answer
3
Building a pushdown automata that receives L*
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it
Ratul Chatterjee
answered
in
Theory of Computation
6 days
ago
by
Ratul Chatterjee
178
views
pushdown-automata
theory-of-computation
context-free-language
0
votes
1
answer
4
selfdoubt
if concatenation of two languages $L_1\ and\ L_2(L_1.L_2)$ is regular then what can we say about $L_1\ and\ L_2 $ ?? is there any possibility of $L_1=nonregular\ ,\ L_2=nonregular \ $ ??
manikantsharma
answered
in
Theory of Computation
Sep 23
by
manikantsharma
557
views
regular-language
0
votes
0
answers
5
GATE CSE 2020
Is this language a regular language ? If yes why and if No why ? The last part is “x!=y” cropped in the picture According to my understanding this is not regular because its says number of x = number of y But Finite automata cant compare the number of x and y here with limited memory. Can you please explain ?
dutta18
asked
in
Theory of Computation
Sep 22
by
dutta18
66
views
number-of-dfa
theory-of-computation
11
votes
4
answers
6
GATE CSE 2020 | Question: 51
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________
dutta18
answered
in
Theory of Computation
Sep 22
by
dutta18
8.2k
views
gatecse-2020
numerical-answers
theory-of-computation
regular-language
0
votes
0
answers
7
Regular expression
Can we simplify a*+a*b(d+ca*b)*ca* ? Where a,b,c,d are regular expression.
nbhatt
asked
in
Theory of Computation
Sep 21
by
nbhatt
57
views
theory-of-computation
finite-automata
regular-expression
0
votes
1
answer
8
Regular expression
What will be the regular expression for following fa using recurrence relation method.
Nisha Bharti
answered
in
Theory of Computation
Sep 21
by
Nisha Bharti
57
views
theory-of-computation
regular-expression
finite-automata
0
votes
1
answer
9
Conversion of Regular expression to Finite Automata
What is the Finite Automata( NFA, epsilon-NFA or DFA) for the regular expression (a*ba)* ?
Sumit Singh Dhami
answered
in
Theory of Computation
Sep 21
by
Sumit Singh Dhami
52
views
theory-of-computation
finite-automata
number-of-dfa
13
votes
4
answers
10
GATE CSE 2022 | Question: 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below? $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$ $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$ $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$ $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$
Prateek pallaw
answered
in
Theory of Computation
Sep 19
by
Prateek pallaw
3.1k
views
gatecse-2022
theory-of-computation
finite-automata
regular-expression
0
votes
1
answer
11
PhD Qualifier Examination, Paper I
Give a context-free grammar for the set of all strings over the alphabet {a, b} with exactly twice as many a’s as b’s. Explain the working of the grammar by characterizing the strings generated by each non-terminal.
afroze
answered
in
Theory of Computation
Sep 17
by
afroze
43
views
theory-of-computation
context-free-grammar
60
votes
4
answers
12
GATE CSE 2008 | Question: 51
Match the following: $\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$} \\\hline \text{F.} & \text{Number of formal ... $\text{E-R, F-P, G-Q, H-S}$ $\text{E-P, F-R, G-S, H-Q}$
Deepak Poonia
answered
in
Theory of Computation
Sep 17
by
Deepak Poonia
10.9k
views
gatecse-2008
normal
theory-of-computation
grammar
0
votes
1
answer
13
please solve
LRU
answered
in
Theory of Computation
Sep 16
by
LRU
52
views
compiler-design
parsing
lr-parser
1
vote
1
answer
14
Turing Machine Rice's Theorem
L = {M|M is a TM that accepts all even numbers} For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. But to show it is Not RE. What ... am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.
manikantsharma
answered
in
Theory of Computation
Sep 16
by
manikantsharma
672
views
decidability
rice-theorem
theory-of-computation
turing-machine
self-doubt
0
votes
1
answer
15
Rice's Theorem
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. According to ... then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?
manikantsharma
answered
in
Theory of Computation
Sep 16
by
manikantsharma
502
views
decidability
rice-theorem
theory-of-computation
self-doubt
1
vote
3
answers
16
Regular expression
Is (a+ab*b)* and (ab*)* same or not?
Hira Thakur
answered
in
Theory of Computation
Sep 16
by
Hira Thakur
198
views
theory-of-computation
regular-expression
finite-automata
5
votes
1
answer
17
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\}$
Deepak Poonia
answered
in
Theory of Computation
Sep 15
by
Deepak Poonia
1.2k
views
gate1988
descriptive
theory-of-computation
finite-automata
difficult
0
votes
0
answers
18
Closure Properties of Languages
Doubt 1: CFL $\cap$ DCFL = CFL CFL - Context Free Languages DCFL - Deterministic Context Free Languages Can you prove above expression Doubt 2: Consider L$_{1}$ = Language generated by a machine M1 L$_{2}$ = Language ... TM Doubt 3: Non Recursively Enumerable Language $\cap$ Any language = Non Recursively Enumerable Language Is this statement correct/always true?
Chaitanya Kale
asked
in
Theory of Computation
Sep 4
by
Chaitanya Kale
103
views
theory-of-computation
2
votes
2
answers
19
ACE ACADEMY: TOC
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ? (a) 4 (b) 16 (c) 20 (d) 24
[ Jiren ]
answered
in
Theory of Computation
Sep 4
by
[ Jiren ]
1.5k
views
theory-of-computation
number-of-dfa
finite-automata
0
votes
2
answers
20
Identification of Regular Language | TOC | Practice Question | Unacademy Class
Which of the following is/are Regular? A] $\left \{ XWYW^{R} \space\ | \space\ W,X,Y \in \left \{ a,b \right \}^{+} \right \}$ ... D] None R => Reverse Please describe your answer.
Srken
answered
in
Theory of Computation
Sep 4
by
Srken
168
views
theory-of-computation
regular-language
0
votes
0
answers
21
#Toc #regularexpression
How to convert (a+b)* into a minimal Dfa
Srken
asked
in
Theory of Computation
Sep 4
by
Srken
71
views
theory-of-computation
regular-expression
finite-automata
0
votes
0
answers
22
Self query
What book should i refer to understand the toc problems i just understand the basics of toc but not be able to solve the problem of toc and cd plz anyone suggest me what book should i follow even after saw the full playlist of toc i am not be able to solve the basic basic problems plz anyone suggest me something To make my toc and cd concept strong
Vaishnavi Gadhe
asked
in
Theory of Computation
Sep 3
by
Vaishnavi Gadhe
57
views
theory-of-computation
0
votes
0
answers
23
PDA | TOC | Practice Question
Identify the type of the given language and draw the corresponding automata for the language. $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$ A] Regular B] DCFL C] CFL but not DCFL D] Non-CFL Please describe your selection.
anupamsworld
asked
in
Theory of Computation
Sep 2
by
anupamsworld
72
views
regular-grammar
context-free-grammar
npda
dpda
theory-of-computation
0
votes
0
answers
24
PDA | TOC | Practice Question | Unacademy Class
Construct PDA using empty stack method for the given language. $L=\left \{ x \space\ | \space\ x\in \left \{ a,b \right \}^{*} ; n_{a}(x) >= n_{b}(x) \right \}$ //number of a’s is greater than or equal to number of b’s
anupamsworld
asked
in
Theory of Computation
Sep 1
by
anupamsworld
45
views
npda
dpda
theory-of-computation
1
vote
1
answer
25
Peter Linz Edition 4 Exercise 1.2 Question 10 (Page No. 28)
Prove or disprove the following claims. (a) $(L_1 ∪ L_2)^R = L_1^R ∪ L_2^R$ for all languages $L_1$ and $L_2$. (b) $(L^R)^* = (L^*)^R$ for all languages $L$.
Deepak Poonia
answered
in
Theory of Computation
Aug 30
by
Deepak Poonia
189
views
peter-linz
peter-linz-edition4
theory-of-computation
proof
1
vote
1
answer
26
Peter Linz Edition 4 Exercise 1.2 Question 8 (Page No. 28)
Prove that $(L_1L_2)^R=L_2^RL_1^R$ for all languages $L_1$ and $L_2$.
Deepak Poonia
answered
in
Theory of Computation
Aug 30
by
Deepak Poonia
133
views
peter-linz
peter-linz-edition4
theory-of-computation
proof
20
votes
6
answers
27
GATE CSE 1996 | Question: 2.8
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one? $L_1.L_2$ $L_1 \cap L_2$ $L_1 \cap R$ $L_1 \cup L_2$
manikantsharma
answered
in
Theory of Computation
Aug 27
by
manikantsharma
4.7k
views
gate1996
theory-of-computation
context-free-language
easy
29
votes
8
answers
28
GATE CSE 1995 | Question: 2.20
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only
manikantsharma
answered
in
Theory of Computation
Aug 27
by
manikantsharma
8.2k
views
gate1995
theory-of-computation
easy
context-free-language
20
votes
4
answers
29
GATE CSE 1992 | Question: 02,xix
Context-free languages are: closed under union closed under complementation closed under intersection closed under Kleene closure
manikantsharma
answered
in
Theory of Computation
Aug 27
by
manikantsharma
3.4k
views
gate1992
context-free-language
theory-of-computation
normal
multiple-selects
19
votes
4
answers
30
GATE CSE 1987 | Question: 2k
State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL.
manikantsharma
answered
in
Theory of Computation
Aug 27
by
manikantsharma
2.2k
views
gate1987
theory-of-computation
context-free-language
true-false
36
votes
9
answers
31
GATE CSE 1991 | Question: 17,b
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
yuyutsu
answered
in
Theory of Computation
Aug 25
by
yuyutsu
9.0k
views
gate1991
theory-of-computation
finite-automata
normal
descriptive
1
vote
2
answers
32
Properties of regular expression | TOC | Doubt
1] ∅^* = ? 2] ∅^+ = ? 3] ∅ . ∈ = ? please describe your answers.
abhinowKatore
answered
in
Theory of Computation
Aug 23
by
abhinowKatore
197
views
theory-of-computation
regular-expression
38
votes
6
answers
33
GATE CSE 2012 | Question: 24
Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive? $1, 2, 3, 4$ $1, 2$ $2, 3, 4$ $3, 4$
gvinay
answered
in
Theory of Computation
Aug 22
by
gvinay
12.5k
views
gatecse-2012
theory-of-computation
decidability
normal
52
votes
11
answers
34
GATE CSE 2003 | Question: 14
The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above
manikantsharma
answered
in
Theory of Computation
Aug 20
by
manikantsharma
13.8k
views
gatecse-2003
theory-of-computation
regular-expression
easy
24
votes
4
answers
35
GATE CSE 2000 | Question: 1.4
Let $S$ and $T$ be languages over $\Sigma=\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$, respectively. Which of the following is true? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \phi$
manikantsharma
answered
in
Theory of Computation
Aug 20
by
manikantsharma
9.3k
views
gatecse-2000
theory-of-computation
regular-expression
easy
35
votes
4
answers
36
GATE CSE 1998 | Question: 1.9
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is true? $A \subset B$ $B \subset A$ $A$ and $B$ are incomparable $A = B$
manikantsharma
answered
in
Theory of Computation
Aug 20
by
manikantsharma
8.9k
views
gate1998
theory-of-computation
regular-expression
normal
0
votes
1
answer
37
Gate cse
Can we construct finite automata for The numbers 1,2,4...2^n,.... Written in unary
pranita-parab
asked
in
Theory of Computation
Aug 14
by
pranita-parab
110
views
normal
0
votes
1
answer
38
Construct a grammar which generates all odd integers up to 999
clendaya
asked
in
Theory of Computation
Aug 11
by
clendaya
82
views
context-free-grammar
0
votes
0
answers
39
TOC doubt
How a language which is not recursively enumerable is uncountable,because as we know every language is a subset of sigma(input alphabet) star which is known to be countable? Please explain I am getting confused in this.
Himanshu555
asked
in
Theory of Computation
Aug 5
by
Himanshu555
55
views
0
votes
1
answer
40
Self Doubt
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$ Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?
tusharb
asked
in
Theory of Computation
Jul 29
by
tusharb
123
views
self-doubt
theory-of-computation
pumping-lemma
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
Aptitude Overflow Book
Participate in Machine Learning benchmarking
GATE Overflow Tikz Templates
UPSC One Time Registration OTR Online Form 2022
DRDO CEPTAM 10 Online Form 2022
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(8.9k)
Digital Logic
(3.2k)
Programming and DS
(5.7k)
Algorithms
(4.5k)
Theory of Computation
(6.5k)
Compiler Design
(2.2k)
Operating System
(4.8k)
Databases
(4.4k)
CO and Architecture
(3.6k)
Computer Networks
(4.4k)
Non GATE
(1.2k)
Others
(2.5k)
Admissions
(644)
Exam Queries
(838)
Tier 1 Placement Questions
(17)
Job Queries
(72)
Projects
(9)
Unknown Category
(851)
Recent questions and answers in Theory of Computation
Recent Blog Comments
@GateOverflow04 link fixed now.
Try...
@Arjun @Deepak Sir, In Test Schedule google...
sir is this for gate? it has way more questions...
https://gateoverflow.in/tag/gate2010 this link is...