Recent questions and answers in Theory of Computation
Register

Recent questions and answers in Theory of Computation

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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 questions and answers in Theory of Computation
    Developed by Chun