menu
Recent questions and answers in Theory of Computation
Login
Register
My account
Edit my Profile
Private messages
My favorites
Register
Recent questions and answers in Theory of Computation
All Activity
Q&A
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Blogs
Previous Year
Exams
Recent questions and answers in Theory of Computation
0
votes
0
answers
39
views
Gate applied
Can some one please do a pumping lema on L = {a^(2n+1) | n>=0 } I know Finite automata can be easily made and hence it is a regular language, but the pumping lema test fails for this implying it is a non-regular language (I am sure I am doing the pumping lema wrong) can someone please do a pumping lema for this so that I compare my solution and rectify my mistake
pavan.varyani
asked
in
Theory of Computation
Dec 7, 2021
by
pavan.varyani
5
points
39
views
toc-languages
regular-expressions
pumping-lemma
0
votes
1
answer
73
views
applied gate test
how many states are in smallest possible DFA {0,1} * {$1^{10}$}
Onika
answered
in
Theory of Computation
Nov 14, 2021
by
Onika
71
points
73
views
toc-languages
regular-expressions
0
votes
1
answer
85
views
TOC - Regular Expressions
As for a Finite Automata, we say a finite automata accepts a language if it accepts all strings present in the language as well as REJECTS all strings which are not present in the language. Is the definition for a regular language the same as that ... all strings of the regular language as well as NOT represent any strings not part of the language ?? Pls clear this.
Awe111
answered
in
Theory of Computation
Oct 29, 2021
by
Awe111
5
points
85
views
toc-languages
regular-expressions
self-doubt
regular-languages
0
votes
1
answer
76
views
Gate Academy toc self douht
Caption I draw a DFA of given language.is it true or false? If i false then send me right one.
udbhav94
answered
in
Theory of Computation
Sep 9, 2021
by
udbhav94
11
points
76
views
toc-languages
nfa-dfa
0
votes
0
answers
71
views
#TOC NPTEL ASSIGNMENT Question about reducibility
Please help me understand this question. I have searched on internet, but no avail.
iarnav
asked
in
Theory of Computation
Sep 7, 2021
by
iarnav
297
points
71
views
theory-of-computation
1
vote
0
answers
26
views
#Theory of computation(DFA)
Construct DFA with ∑ = {0, 1} accepts the strings with an even number of 0's followed by single 1.
Urvesh
asked
in
Theory of Computation
Aug 24, 2021
by
Urvesh
9
points
26
views
finite-automata
0
votes
0
answers
63
views
class excercise
Write a regular expression for all strings of 0’s and 1’s that are of odd length
brightborn
asked
in
Theory of Computation
Aug 24, 2021
by
brightborn
5
points
63
views
regularexpression
0
votes
0
answers
195
views
Countability in toc
Hi What is best resource and Where to study countability topic in toc?
ykrishnay
asked
in
Theory of Computation
Aug 21, 2021
by
ykrishnay
103
points
195
views
self-doubt
finite-automata
toc-languages
theory-of-computation
0
votes
0
answers
39
views
How to design Turing machine for addition of 2 binary numbers
ykrishnay
asked
in
Theory of Computation
Aug 18, 2021
by
ykrishnay
103
points
39
views
turing-machine
self-doubt
compiler-design
toc-languages
finite-automata
1
vote
0
answers
53
views
complement of language
How to find complement of language.? complement of recursive language is recursive. while complement of context free language is context sensitive language.
TheShivam
asked
in
Theory of Computation
Aug 16, 2021
by
TheShivam
9
points
53
views
self-doubt
toc-languages
regular-languages
context-free-languages
turing-machine
0
votes
0
answers
35
views
Made easy Test Series 2021
Consider the two languages L1 and L2 where L1 is regular and L2 is DCFL. Then the language L3 = (L1 ∩ L2*)’ is/are true about L3? CSL CFL Recursive Recursively enumerable
DKY123
asked
in
Theory of Computation
Aug 13, 2021
by
DKY123
15
points
35
views
made-easy-test-series
0
votes
0
answers
121
views
Made easy Test Series 2021
Consider a Language L1 which is Regular and L2 which is DCFL. We perform the following operations on these languages. The resultant language we get in L7 is/are (choose all possible options) Regular DCFL CFL CSL
DKY123
asked
in
Theory of Computation
Aug 13, 2021
by
DKY123
15
points
121
views
made-easy-test-series
0
votes
0
answers
52
views
Made easy Test Series 2021
Let L1 be the language corresponding to the regular expression (0 + 1)* 001* and L2 be the language corresponding to the regular expression 110(1 + 0)*. Which of the following is the regular expression corresponding to the language L1 ∩ L2? (0 + 1)* 00110(1 – 10)* 110(1 + 0)* 001* 110001* None of the above
DKY123
asked
in
Theory of Computation
Aug 13, 2021
by
DKY123
15
points
52
views
made-easy-test-series
0
votes
0
answers
21
views
Made easy Test Series 2021
Consider the regular expression: R=(ab|abb)*bbab Which of the following string in not in the set denoted by R? abbabbbab abbababbbab abababababababababab ababababbab
DKY123
asked
in
Theory of Computation
Aug 13, 2021
by
DKY123
15
points
21
views
made-easy-test-series
0
votes
0
answers
43
views
Ace TEST Series 2022
Which of the following problem can be solved by standard greedy algorithm. A ) B ) C ) D )
DKY123
asked
in
Theory of Computation
Aug 13, 2021
by
DKY123
15
points
43
views
ace-academy-test-series
0
votes
0
answers
38
views
ACE TEST SERIES 2022
What is the number of distinct minimal spanning trees possible for the above graph using Kruskal’s algorithm. A ) B ) C ) D )
DKY123
asked
in
Theory of Computation
Aug 13, 2021
by
DKY123
15
points
38
views
ace-academy-test-series
0
votes
0
answers
25
views
Cse doubts knowledge gate youtube
How many 2 state DFA's can be constructed with a designated initial final state and designated final state over alphabet {a,b}? Now I want to ask that what means is "designated initial state " Or "designated final state"?
ykrishnay
asked
in
Theory of Computation
Aug 7, 2021
by
ykrishnay
103
points
25
views
theory-of-computation
self-doubt
language
0
votes
0
answers
45
views
Regular Grammar
Is S--> AccB A-->aA/a B-->bB/a a regular grammar according to the type 3 grammar rule i.e, production must be in the form S-->Ax or S-->xA where A is non terminal and x is terminal?
Shubhranshu
asked
in
Theory of Computation
Aug 1, 2021
by
Shubhranshu
5
points
45
views
toc-languages
regular-languages
regular-grammar
0
votes
0
answers
77
views
Describe the language corresponding to following (1+01)*(0+01)*
Ashutosh1106
asked
in
Theory of Computation
Jul 23, 2021
by
Ashutosh1106
5
points
77
views
theory-of-computation
0
votes
0
answers
86
views
A={ww^rw^rw|w belong to £*} is CFL or not
Any one can solve this question please give brief explanation for this question
Bulbul123
asked
in
Theory of Computation
Jul 22, 2021
by
Bulbul123
5
points
86
views
theory-of-computation
context-free-languages
0
votes
0
answers
22
views
#SELF_DOUBT_FROM_RICE_THEOREM
If a language satisfies monotonic property then is it REL or REC or NOT REL ?? And What about CO- REL?? #RICE THEOREM
princeit07
asked
in
Theory of Computation
Jul 12, 2021
by
princeit07
5
points
22
views
ricestheorem
0
votes
0
answers
52
views
Theory of computation Dpda
Can anyone make Dpda for the following languages L1={ a^nb^m| n>m;n,m>0} L2= { x ∈ { a, b }* | na (x) > nb (x) } I have find too little solution and but everyone violating Dpda definition like for any q€Q ,x€ T( stack symbol ) if, ∆(q, epsilon,x) !=phi then ∆(q,a,x)= phi for every a€sigma Please anyone help...
juuniversity
asked
in
Theory of Computation
Jul 6, 2021
by
juuniversity
5
points
52
views
self-doubt
0
votes
0
answers
23
views
An introduction to formal languges
Construct Turing machines that will accept the following languages on {a, b}. L= {w|w| is even}.
Rahul_18
asked
in
Theory of Computation
Jul 1, 2021
by
Rahul_18
5
points
23
views
peter-linz
turing-machine
0
votes
0
answers
53
views
Self doubt.
What are the differences between a dead state and a trap state?
raja11sep
asked
in
Theory of Computation
Jun 30, 2021
by
raja11sep
5
points
53
views
self-doubt
finite-automata
0
votes
0
answers
22
views
Simple explanation of decidable, undecidable, recognizable and unrecognizable
sayuri
asked
in
Theory of Computation
Jun 26, 2021
by
sayuri
5
points
22
views
theory-of-computation
decidability
turing-machine
0
votes
0
answers
68
views
MadeEasy TOC question
hi, this is MadeEasy TOC question. It mentions to eliminate X first and then Y. How can this be done, I mean how can we eliminate X and Y since even after subsitution they will be repeating. I know here we have to use arden’s theorem but unable to understand how to reduce. Please help…....….
rish1602
asked
in
Theory of Computation
Jun 25, 2021
by
rish1602
9
points
68
views
ardens-theorem
theory-of-computation
made-easy-test-series
regular-expressions
1
vote
1
answer
725
views
GATE CSE 2021 Set 1 | Question: 1 | Video Solution
amitkhurana512
answered
in
Theory of Computation
Jun 24, 2021
by
amitkhurana512
173
points
725
views
gate2021-cse-set1
context-free-languages
theory-of-computation
0
votes
0
answers
41
views
pumping lemma
@Praveen Saini @Lakshman Patel RJIT @Digvijay Pandey Just wanted to ask doubt, If the minimum pumping length of the language can be 0 for any language? I think it should not be as any string will either be accepted or rejected.
rish1602
asked
in
Theory of Computation
Jun 21, 2021
by
rish1602
9
points
41
views
pumping-lemma
pumping-length
theory-of-computation
self-doubt
3
votes
1
answer
860
views
GATE CSE 2021 Set 1 | Question: 12 | Video Solution
amitkhurana512
answered
in
Theory of Computation
Jun 18, 2021
by
amitkhurana512
173
points
860
views
gate2021-cse-set1
multiple-selects
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
0
answers
35
views
Clear distinction between Finite automata, Regular expressions
akshansh
asked
in
Theory of Computation
Jun 12, 2021
by
akshansh
15
points
35
views
toc-languages
regular-expressions
nfa-dfa
0
votes
0
answers
59
views
NPTEL(Theory of Computation )
How is the regular expression (0+1)*0(0+1)*1(0+1)* is equivalent to (0+1)*01(0+1)* ?
hrtoimukra
asked
in
Theory of Computation
Jun 9, 2021
by
hrtoimukra
5
points
59
views
toc-languages
0
votes
0
answers
35
views
can we make DFA for a language where there is comparion between symbols but lanuage is finite a^nb^n;n<=3
promise
asked
in
Theory of Computation
Jun 8, 2021
by
promise
5
points
35
views
regular
language
0
votes
0
answers
60
views
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
promise
asked
in
Theory of Computation
Jun 8, 2021
by
promise
5
points
60
views
nfa-dfa
regular-languages
regular-grammar
finite-automata
0
votes
0
answers
26
views
#Ullman #RegularLanguage
It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?
Palash Nandi 1
asked
in
Theory of Computation
May 29, 2021
by
Palash Nandi 1
13
points
26
views
self-doubt
theory-of-computation
0
votes
0
answers
45
views
#Ullman #Homomorphism
Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?
Palash Nandi 1
asked
in
Theory of Computation
May 29, 2021
by
Palash Nandi 1
13
points
45
views
#cfl
1
vote
1
answer
24
views
#Ullman #RegularLanguage
Please Correct me if Logic is wrong. Let w = w1.w2.w3...wk, By definition of min(L), w ∈ L but any w1.w2.w3...w(k-1) doesn’t. Then NO prefix reach any final state regardless of their length. Using only prefixes of w drawing a dfa is not possible but w itself belongs to L and min(L). So dfa of min(L) exists.=> Closed.
Deepak Poonia
answered
in
Theory of Computation
May 29, 2021
by
Deepak Poonia
1.7k
points
24
views
#cfl
0
votes
0
answers
16
views
#Ullman #TOC #RegularLanguage
Check if max(L) is closed or not for max(L) : { w| w is in L but no x other than EmptyString, wx is in L }. Correct if Logic is wrong., If wx is not in L ( except x is empty ) i.e. x forces the flow to stop at a non-Final state. So unless x is ... on a final state, so is w alone. A dfa is possible for all w' in L => dfa is possible for w' for max(L) => Closed.
Palash Nandi 1
asked
in
Theory of Computation
May 29, 2021
by
Palash Nandi 1
13
points
16
views
self-doubt
0
votes
0
answers
22
views
#Ullman #RegularLanguage
check if init(L) is closed or not where init(L) = { w | for some x, wx is in L } => Correct if Logic is wrong. Let there are n differnt state in dfa of L. Case_1: if len( wx ) >= n and wx is in L then x is either EmptyString or ... is EmptyString else whether single w' reach the final state is undecidable. So., x is Empty for sure, for all w in init(L) => Closed.
Palash Nandi 1
asked
in
Theory of Computation
May 29, 2021
by
Palash Nandi 1
13
points
22
views
self-doubt
0
votes
0
answers
26
views
#Ullman #Homorphism
Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?
Palash Nandi 1
asked
in
Theory of Computation
May 27, 2021
by
Palash Nandi 1
13
points
26
views
#cfl
1
vote
1
answer
28
views
Self Doubt : Push Down Automata
In place of highlighted transition can we use the below transitions: epsilon,a|a , epsilon,b|b , epsilon,z0|z0 ?
Deepak Poonia
answered
in
Theory of Computation
May 24, 2021
by
Deepak Poonia
1.7k
points
28
views
non-determinism
#cfl
To see more, click for all the
questions in this category
.
Ask a Question
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
2022 May 23 - 29
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
Search GATE CSE Doubts