Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions and answers in Theory of Computation
0
votes
0
answers
ACE Test Series
What is the minimum no of states in DFA which accepts the language generated by reg exp (0*1)*1(0+1)* ?. Is this binary strings containing 1? Pls Answer.
asked
Feb 9
in
Theory of Computation
by
akashks
(
5
points)
|
26
views
test-series
0
votes
1
answer
Context Free Languages (Self Doubt)
I understand that the language L = {a^m b^n c^k|(m=n)or(n=k)} is CFL because it can be represented as the union of L1 = {a^m b^m c^k} and L2 = {a^m b^k c^k} which are both CFL's. But I can't figure out the working of the PDA accepting L. To check ... meaning (m=n) or (m-n) a's or (n-m) b's will remain in the stack meaning (m!=n). How can we check for (n=k) now?
answered
Feb 7
in
Theory of Computation
by
Ollie
(
525
points)
|
37
views
toc-languages
selfdoubt
0
votes
0
answers
Made easy test series
Consider the following problems and select the problem which is recursively enumerable but not recursive. (MSQ type) 1 . Whether a given Turing machine accepts non-empty language. 2. Whether a given Turing machine accepts finite language . 3. Whether a given Turing machine accepts at most 10 strings 4. Whether a given Turing machine accepts at least 10 strings.
asked
Feb 4
in
Theory of Computation
by
gajendercse
(
41
points)
|
44
views
decidability
selfdoubt
0
votes
0
answers
Practise Question from Ulman
Please give the DFA and regular expression
asked
Feb 4
in
Theory of Computation
by
chandra sai
(
5
points)
|
11
views
dfas
0
votes
0
answers
made easy test series
Answer given is “All of these” My answer is none of these are regular.
asked
Feb 3
in
Theory of Computation
by
rahul65
(
5
points)
|
19
views
toc-languages
0
votes
0
answers
ACE Test Series
$A. Regular$ $B. CSL but not CFL$ $C. CFL$ $D. CSL$ Solution given is
[closed]
asked
Feb 2
in
Theory of Computation
by
Parth27
(
163
points)
|
21
views
test-series
0
votes
0
answers
TOC Made easy
Consider the grammar consisting of seven productions. S → aA | aBB A → aaA | λ B → bB | bbC C → B After elimination of unit, useless, and λ -productions how many productions remain in the resulting grammar ? 2 3 4 5
asked
Feb 2
in
Theory of Computation
by
kirtipurohit
(
7
points)
|
19
views
test-series
toc-languages
0
votes
0
answers
TOC | CSL Complement | Ace Pre Gate Question
The complemment of the language {wwww|w is in (
[email protected]
+$)*} is Regular CSL but not CFL CFL CSL Answer Can someone please explain how this language is CFL ?
asked
Feb 1
in
Theory of Computation
by
Sam_Gate21
(
5
points)
|
27
views
selfdoubt
0
votes
0
answers
Gate Overflow itself
Is the explanation is correct? Link-https://gateoverflow.in/33183/complement-of-csl If I say complement of $a^{n}b^{n}c^{n} \, \, \, \, \, \, is\, \, \, \, \, a^{n}b^{n}c^{m} \: \: and\: \: \: m\neq n$ Then How Can it be regular?
asked
Feb 1
in
Theory of Computation
by
RavGopal
(
145
points)
|
23
views
toc-languages
+1
vote
1
answer
Output Of Turing Machine : Ace Academy Subject Wise Test Series
answered
Feb 1
in
Theory of Computation
by
Parth27
(
163
points)
|
27
views
turing-machine
0
votes
0
answers
self doubt - decidability
L={<M>| M is a TM that accepts all even numbers}. How to check whether it is RE, REC or not RE… I think Rice’s theorem 2nd part is not applicable here
asked
Feb 1
in
Theory of Computation
by
Abhineet Singh
(
23
points)
|
21
views
decidability
toc-languages
+1
vote
0
answers
Recursive Languages Self Doubt
Is recursive language closed under positive closure?
asked
Jan 29
in
Theory of Computation
by
aditi19
(
53
points)
|
23
views
toc-languages
+1
vote
1
answer
Applied AI ALL INDIA MOCK TEST
In option b, it can generate any string where a can be followed by b & then c or b followed by a & then c , c by a & then b i.e sequence od characters isn’t fixed. Does it have a CFG for it?
answered
Jan 25
in
Theory of Computation
by
Sahil91
(
683
points)
|
20
views
#cfl
0
votes
0
answers
Madeeasy Test series TOC Q1
asked
Jan 23
in
Theory of Computation
by
Shivateja MST
(
45
points)
|
10
views
toc-languages
+1
vote
1
answer
Peter Linz Ex-7.3 Q6 CFL
L=$a^nb^{2n} | n\geq 0$ is a DCFL. Show that L* is DCFL
answered
Jan 23
in
Theory of Computation
by
zxy123
(
3.2k
points)
|
26
views
peter-linz
dcfl
+1
vote
1
answer
Made easy test series
Can anyone draw the DFA’s for the question mentioned?
answered
Jan 22
in
Theory of Computation
by
zxy123
(
3.2k
points)
|
32
views
finite-automata
0
votes
0
answers
CFG Self-doubt
As per the definition of CNF and GNF, these grammars doesn’t allows $\epsilon$ productions. What if the language contains $\epsilon$? In that case how do we convert the CFG to CNF and GNF? Can someone explain with an example?
asked
Jan 20
in
Theory of Computation
by
aditi19
(
53
points)
|
18
views
cfg
0
votes
1
answer
Show that the language S-> aSS| b is not regular ?
answered
Jan 20
in
Theory of Computation
by
SarathBaswa
(
849
points)
|
19
views
toc-languages
peterlinz
0
votes
0
answers
An introduction to formal languages and automata
How can I explain that this language- L= { a<sup>n</sup> b<sup>l</sup> : n ≠ l } is not regular. [USE PUMPING LEMMA OR CLOSURE PROPERTIES] This question is under a book named An introduction to ... understandable manner and show how you exactly arrived at the solution? That would be a great help to me. Thanks in advance
asked
Jan 18
in
Theory of Computation
by
kirtipurohit
(
7
points)
|
9
views
toc-languages
peter-linz
grammar
dfas
pumping-lemma
0
votes
1
answer
Does Left recursive grammar same as left linear grammar
answered
Jan 17
in
Theory of Computation
by
wander
(
301
points)
|
14
views
selfdoubt
0
votes
0
answers
An introduction to formal languages and automata peter linz
asked
Jan 16
in
Theory of Computation
by
kirtipurohit
(
7
points)
|
26
views
toc-languages
peter-linz
grammar
dfas
nfa-dfa
0
votes
0
answers
Peter Linz 5e Ex-2.1 Q-7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }
[closed]
asked
Jan 14
in
Theory of Computation
by
aditi19
(
53
points)
|
10
views
peter-linz
toc-languages
dfas
+1
vote
0
answers
Peter Linz 5e Ex-2.1 Q7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }
asked
Jan 14
in
Theory of Computation
by
aditi19
(
53
points)
|
29
views
peter-linz
toc-languages
dfas
0
votes
1
answer
Ace test series
[closed]
answered
Jan 7
in
Theory of Computation
by
Abhisheksmile94
(
347
points)
|
35
views
test-series
0
votes
0
answers
Ace Test Series
Is C Valid Answer? I feel regular expression in C can also Generate 11 which is not there in language so the answer should be D only….Is my reasoning valid if not please help to clear this concept...
asked
Jan 6
in
Theory of Computation
by
vipin.gautam1906
(
9
points)
|
37
views
dfadesign
0
votes
0
answers
Self doubt on decidability of turing machine and dfa
asked
Jan 5
in
Theory of Computation
by
meivinay
(
5
points)
|
58
views
decidability
turing-machine
selfdoubt
0
votes
1
answer
Applied Test Series TOC
Options: My answer was: D answer according to them was B and D and their explaination was
answered
Jan 4
in
Theory of Computation
by
Abhisheksmile94
(
347
points)
|
28
views
test-series
toc-languages
0
votes
0
answers
GATE 2003 , Theory Of Computation , Turing Machine
asked
Jan 4
in
Theory of Computation
by
Pushkar Khadase
(
5
points)
|
29
views
toc-languages
turing-machine
0
votes
1
answer
Theory of automata
Convert the Following DFA to Regular Expression using GNFA.
answered
Jan 3
in
Theory of Computation
by
Abhisheksmile94
(
347
points)
|
42
views
finite-automata
toc-languages
0
votes
2
answers
TOC- closure properties of RL
let L1=a^n (which is a regular language) and L2=b^n (which is also a regular language) L1.L2 is also regular.. how?? as (a^nb^n) is not a regular language
answered
Jan 3
in
Theory of Computation
by
Abhisheksmile94
(
347
points)
|
49
views
selfdoubt
toc-languages
0
votes
3
answers
youtube exercise unacademy
L1=a^n,,n>0 L2=a^n b^n c^n , n>0 L1.L2 is a)regular b)cfl c)csl d)none
answered
Jan 3
in
Theory of Computation
by
Abhisheksmile94
(
347
points)
|
44
views
toc-languages
0
votes
0
answers
My college homework
1) Let ∑ = {D , L}. Find a DFA that accepts Password (P) with the following conditions: - | P | ≥ 4 - P begins with a letter and ends with a letter. - P contains at least one digit. 2) Let ∑ = { 0..9 , ... the following DFA that has access to the laboratories of company controlled. The employee number becomes read as a binary number. Which employee numbers are accepted.
asked
Dec 29, 2020
in
Theory of Computation
by
MotasemMobayyed
(
5
points)
|
11
views
finite-automata
0
votes
1
answer
KLP MISHRA #TOC #Precedence of operators #computaion
answered
Dec 23, 2020
in
Theory of Computation
by
Harshal Vora
(
11
points)
|
14
views
computation
theory
0
votes
0
answers
lIntroduction to Languages and The Theory of Computation
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)
|
12
views
grammar
0
votes
0
answers
Introduction to Languages and The Theory of Computation
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)
|
6
views
toc-languages
0
votes
0
answers
Introduction to Languages and The Theory of Computation John C. Martin North Dakota State University
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)
|
9
views
toc-languages
0
votes
0
answers
John C. Martin 4.9
4.9. Suppose that G1 = (V1, {a, b}, S1, P1) and G2 = (V2, {a, b}, S2, P2) are CFGs and that V1 ∩ V2 = ∅. a. It is easy to see that no matter what G1 and G2 are, the CFG Gu = (Vu, {a, b}, Su, Pu) defined by Vu = V1 ∪ V2, Su = S1, and Pu = P1 ∪ ... {S1 → S1S1 | } generates every string in L(G1) ∗. Find a grammar G1 with V1 = {S1} and a string x ∈ L(G ∗ ) such that x /∈ L(G) ∗.
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)
|
7
views
data-structures
0
votes
0
answers
Introduction to Languages and The Theory of Computation John C. Martin
asked
Dec 23, 2020
in
Theory of Computation
by
aryan1234
(
5
points)
|
8
views
toc-languages
0
votes
1
answer
This was asked in ace academy test series, but no suitable explaination was provided. Kindly enlighten!
answered
Dec 22, 2020
in
Theory of Computation
by
Deepakk Poonia (Dee)
(
1.5k
points)
|
35
views
toc-
0
votes
1
answer
#selfdoubt #regular_toc_languages
answered
Dec 21, 2020
in
Theory of Computation
by
Sahil91
(
683
points)
|
26
views
selfdoubt
toc-languages
To see more, click for all the
questions in this category
.
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
2021 Feb 22 - 28
Enolx.21
12 Points
rapidxy
9 Points
zxy123
6 Points
adas7099
4 Points
Shinichi_Kudo
2 Points
Deepakk Poonia (Dee)
2 Points
Weekly Top User (excluding moderators) will get free access to
GATE Overflow Test Series for GATE 2021
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
Recent questions and answers in Theory of Computation
9,095
questions
3,154
answers
14,583
comments
95,939
users