Recent questions and answers in Theory of Computation

Recent questions and answers in Theory of Computation

0 votes

1 answer 40 views

applied gate test
how many states are in smallest possible DFA {0,1} * {$1^{10}$}

Onika answered in Theory of Computation Nov 14

by Onika

5 points

40 views

0 votes

1 answer 45 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

by Awe111

5 points

45 views

0 votes

1 answer 57 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

5 points

57 views

0 votes

0 answers 44 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

by iarnav

297 points

44 views

1 vote

0 answers 19 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

by Urvesh

9 points

19 views

0 votes

0 answers 44 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

5 points

44 views

0 votes

0 answers 173 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

103 points

173 views

0 votes

0 answers 31 views

How to design Turing machine for addition of 2 binary numbers

ykrishnay asked in Theory of Computation Aug 18

103 points

31 views

1 vote

0 answers 37 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

9 points

37 views

0 votes

0 answers 31 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

by DKY123

15 points

31 views

0 votes

0 answers 115 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

by DKY123

15 points

115 views

0 votes

0 answers 47 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

by DKY123

15 points

47 views

0 votes

0 answers 15 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

by DKY123

15 points

15 views

0 votes

0 answers 26 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

by DKY123

15 points

26 views

0 votes

0 answers 28 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

by DKY123

15 points

28 views

0 votes

0 answers 21 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

103 points

21 views

0 votes

0 answers 33 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

5 points

33 views

0 votes

0 answers 55 views

Describe the language corresponding to following (1+01)*(0+01)*

Ashutosh1106 asked in Theory of Computation Jul 23

by Ashutosh1106

5 points

55 views

0 votes

0 answers 37 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

5 points

37 views

0 votes

0 answers 19 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

5 points

19 views

0 votes

0 answers 49 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

by juuniversity

5 points

49 views

0 votes

0 answers 19 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

5 points

19 views

0 votes

0 answers 34 views

Self doubt.
What are the differences between a dead state and a trap state?

raja11sep asked in Theory of Computation Jun 30

5 points

34 views

0 votes

0 answers 14 views

Simple explanation of decidable, undecidable, recognizable and unrecognizable

sayuri asked in Theory of Computation Jun 26

by sayuri

5 points

14 views

0 votes

0 answers 45 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

9 points

45 views

1 vote

1 answer 717 views

GATE CSE 2021 Set 1 | Question: 1 | Video Solution

amitkhurana512 answered in Theory of Computation Jun 24

by amitkhurana512

173 points

717 views

0 votes

0 answers 26 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

9 points

26 views

3 votes

1 answer 844 views

GATE CSE 2021 Set 1 | Question: 12 | Video Solution

amitkhurana512 answered in Theory of Computation Jun 18

by amitkhurana512

173 points

844 views

0 votes

0 answers 31 views

Clear distinction between Finite automata, Regular expressions

akshansh asked in Theory of Computation Jun 12

15 points

31 views

0 votes

0 answers 43 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

5 points

43 views

0 votes

0 answers 22 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

5 points

22 views

0 votes

0 answers 40 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

5 points

40 views

0 votes

0 answers 20 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

by Palash Nandi 1

13 points

20 views

0 votes

0 answers 19 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

by Palash Nandi 1

13 points

19 views

1 vote

1 answer 19 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.

Deepakk Poonia (Dee) answered in Theory of Computation May 29

by Deepakk Poonia (Dee)

1.7k points

19 views

0 votes

0 answers 13 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

by Palash Nandi 1

13 points

13 views

0 votes

0 answers 16 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

by Palash Nandi 1

13 points

16 views

0 votes

0 answers 22 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

by Palash Nandi 1

13 points

22 views

1 vote

1 answer 22 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 ?

Deepakk Poonia (Dee) answered in Theory of Computation May 24

by Deepakk Poonia (Dee)

1.7k points

22 views

0 votes

1 answer 16 views

#Self_Doubt #NFA
For any given NFA with ip_set = {a,b} if any transaction is Missing then can we assume a Self Loop ? For example, [T1] a b [T2] a b S S,P Q S S,P Q is P _ Q same as P P Q Q* _ _ Q* Q Q Notice in T1 for transaction(P,a) = undefined. So can we assume transaction(P,a) = P ?

Kanwae Kan answered in Theory of Computation May 19

5 points

16 views

To see more, click for all the questions in this category.

Recent questions and answers in Theory of Computation

Search GATE CSE Doubts