Recent questions and answers in Theory of Computation - GATE CSE Doubts

0 votes

2 answers

Applied course test series : Regular language
What will be the answer for above question?

answered 2 hours ago in Theory of Computation by Pratyush Priyam Kuan (398 points) | 16 views

0 votes

0 answers

#Self_doubt#Decidability
L1={<M>| M is TM and M doesnt accept all even nos} L2={<M>| M is TM and M rejects all even nos} I think we need to check for infinite no of steps so both not RE?Dont knw the answer plz confirm

asked 2 days ago in Theory of Computation by nandani17 (13 points) | 7 views

0 votes

0 answers

Self doubt in pumping lemma
a^nb^2n where n > 1 , is regular language or not how to proof using pumping lemma

asked 4 days ago in Theory of Computation by Sandeep Verma (13 points) | 9 views

0 votes

0 answers

TOC undecidability
If L is Turing-recognizable. Then (a) L and L̅ must be decidable. (b) L must be decidable but L̅ need not be. (c) Either L is decidable or L̅ is not Turing recognizable. (d) None of above. [closed]

asked 5 days ago in Theory of Computation by Shubhm (23 points) | 8 views

0 votes

0 answers

Applied course test series : Context free grammar
A) I and II only B) II and III only C) I and III only D) I,II and III Please give answer and explaination for above question.

asked 6 days ago in Theory of Computation by vishal burnwal (58 points) | 13 views

0 votes

0 answers

self doubt regular grammar
Can a regular grammar be ambiguous? If so then plz give some example.

asked 6 days ago in Theory of Computation by Shubhm (23 points) | 14 views

0 votes

0 answers

DFA/NFA MINIMUM NUMBER OF STATES
How to decide minimum when will DFA have N+2 or N+1 states? https://gateoverflow.in/39562/gate2016-2-16 https://gateoverflow.in/8256/gate2015-2-53 https://gateoverflow.in/118302/gate2017-1-22 https://gateoverflow.in/118160/gate2017-2-25 above 2 are cases for N+1 and latter are N+2

asked 6 days ago in Theory of Computation by Asim Siddiqui 4 (8 points) | 5 views

0 votes

1 answer

Made easy test series : Decidability
Can some one explain (IV) is decidable or not?

answered Dec 5 in Theory of Computation by Priyansh Singh (122 points) | 18 views

0 votes

0 answers

Made easy test series 2020- Finite Automata
A) None of the above B) I & II only C) I & III only D) All of the above What is the correct answer for above question ,Plz explian?

asked Dec 5 in Theory of Computation by vishal burnwal (58 points) | 12 views

0 votes

0 answers

ACE GATE Mock Test 10 Q27 Binary tree
How to draw the tree from this representation?

asked Dec 4 in Theory of Computation by DukeThunders (288 points) | 15 views

0 votes

0 answers

ACE GATE Mock Test 10 Q15 Converting machines
Answer is given as C. But how can a FA be converted to PDA. Doesn’t it imply that FA and PDA are equivalent in power which is wrong.. Also not getting what they are tryint to say. How can a DPDA be converted to NPDA

asked Dec 4 in Theory of Computation by DukeThunders (288 points) | 7 views

0 votes

0 answers

ACE GATE Mock Test 10 Q12 Decidability

asked Dec 4 in Theory of Computation by DukeThunders (288 points) | 9 views

+1 vote

0 answers

Test by Bikram 2017: Theory of Computation Test 1-16

asked Dec 4 in Theory of Computation by !KARAN (159 points) | 13 views

0 votes

1 answer

ME test series TOC
Given regular expression for the language is : a(a+b)$^{*}$+ba(a+b)$^{*}$+bb(a+b)$^{*}$ . Is this correct ?? as the DFA do not accept “bba” string but regular expression contain it. Do we have to consider dead state also while writing the regular expression for DFA ??

answered Dec 3 in Theory of Computation by Pratyush Priyam Kuan (398 points) | 11 views

+1 vote

2 answers

Minimum pumping length
Find minimum pumping length of $\text{L(a*bb)}$

answered Dec 3 in Theory of Computation by Sandeep Verma (13 points) | 54 views

0 votes

0 answers

MOCK TEST-SERIES
Which of the following language(s) generates more than one parse tree for a string ? L1 = {a^nb^mc^md^n ∈ {a, b, c, d}* | n, m ≥ 0} ∪ {a^nb^nc^md^m ∈ {a, b, c, d}* | n, m ≥ 0} L2 = {a^nb^mc^m ∈ {a, b, c}* | n, m ≥ 0} ∪ {a^nb^nc^m ∈ {a, b, c}* | n, m ≥ 0} ... ∪ {a^nb^mc^p ∈ {a, b, c}* | m ≠ p; n, m ≥ 0} (A) Only L1 and L2 (B) Only L1 and L3 (C) Only L2 and L3 (D) All L1, L2, and L3

asked Dec 2 in Theory of Computation by Dipanshu Rana (24 points) | 10 views

0 votes

0 answers

#MOCK TEST-SERIES
A regular expression is ambiguous when there exists a string which can be constructed in two different ways from the regular expression. Which of the following regular expressions are unambiguous? a)a((ab)*cd)* ∪ a(ababcb*)*a* b)aab*(ab)* ∪ ab* ∪ a*bba* c)aaba* ∪ aaaba ∪ aabba* ∪ a d)None

asked Dec 2 in Theory of Computation by Dipanshu Rana (24 points) | 6 views

0 votes

1 answer

GATE GURU 201: TOC
How to perform concatenation of 2 languages? and what will be the ans?

answered Dec 2 in Theory of Computation by chandrikabhuyan8 (117 points) | 21 views

0 votes

0 answers

String acceptance in PDA
In PDA is it okay that stack is not empty but string reached the final state? Can we accept such string?

asked Dec 2 in Theory of Computation by luc_Bloodstone (27 points) | 13 views

0 votes

0 answers

TOC: GATEGURU 201

asked Dec 1 in Theory of Computation by Debapaul (310 points) | 10 views

0 votes

0 answers

GATE GURU: TOC 103
Ans given is $1$, but how can we say S1 is also regular? say $L=a^*b^*$ and x=$a^nb^n$ and $y= ϵ$, so $x.y =a^nb^n$ then how can S1 be regular?

asked Dec 1 in Theory of Computation by Debapaul (310 points) | 28 views

0 votes

0 answers

GATE GURU: TOC SUBJECT

asked Dec 1 in Theory of Computation by Debapaul (310 points) | 5 views

0 votes

2 answers

TOC GATE GURU
Let $r$ be a regular language, then which of the following statements is/are $TRUE$? $S1:$ There exist $x$ which satisfies the property $r+x=x$ for every $r$ $S2:$ There exist $x$ which satisfies the property $r.x=x$ for every $r$ [closed]

answered Dec 1 in Theory of Computation by Priyansh Singh (122 points) | 13 views

0 votes

0 answers

Minimum Pumping length: GATE OVERFLOW
What is the minimum pumping length of the following? $S_1:$ $01(01^*0)^*1$ $S_2$ : $(01)^*$

asked Dec 1 in Theory of Computation by Debapaul (310 points) | 40 views

0 votes

0 answers

CS GATE GURU: TOC

asked Nov 30 in Theory of Computation by Debapaul (310 points) | 19 views

0 votes

0 answers

GATE GURU: TOC 102
Ans given $4$ but how can it be? Shouldn’t it be $3$?

asked Nov 30 in Theory of Computation by Debapaul (310 points) | 11 views

0 votes

0 answers

GATE GURU: TOC 101
See r4 is ϵ , whereas r5 is ( ϵ + Φ ) , so $NONE$ is correct right? as r5 can be $phi$ as well as $epsilon$ but r4 can only be $epsilon$ Is my approach correct?

asked Nov 30 in Theory of Computation by Debapaul (310 points) | 16 views

0 votes

0 answers

#made esay face gate quiz
Given explain and

asked Nov 29 in Theory of Computation by amit166 (113 points) | 15 views

0 votes

1 answer

ACE Test Series Test 26 Q15 TOC

answered Nov 29 in Theory of Computation by Mk Utkarsh (302 points) | 30 views

0 votes

1 answer

ACE Test Series Test 26 Q30 TOC
In this they are calling all the options as inherently unambiguous. But does there exist any umambi grammar for option C? It can’t be accepted by DPDA right?

answered Nov 29 in Theory of Computation by Vimal Patel (389 points) | 16 views

0 votes

1 answer

ACE Test Series Test 26 Q25 TOC
They have given that both are correct but how is it so? There are some CFL which are inherently ambiguous. So how can there exist an unambi grammar for such languages?

answered Nov 29 in Theory of Computation by Vimal Patel (389 points) | 34 views

0 votes

0 answers

ACE Test Series Test 26 Q26 TOC

asked Nov 28 in Theory of Computation by DukeThunders (288 points) | 16 views

0 votes

0 answers

ACE Test Series Test 26 Q14 TOC
I’m a bit confused with this question. How to answer is if transition from the initial states are not given. I assumed that transitions from inital states lead to rest of of the 99 non final states hence my answer was epsilon. But if I assume both 0,1 transition from intial state loops on itself then answer will be sigma*. Then can i go with option D?

asked Nov 28 in Theory of Computation by DukeThunders (288 points) | 11 views

0 votes

0 answers

SELF DOUBT LR(K) PREVIOUS YEAR
https://gateoverflow.in/2597/gate1995-1-10 PLEASE SEE HOW TO CHECK LR(K) OR NOT??

asked Nov 28 in Theory of Computation by eyeamgj (17 points) | 20 views

0 votes

0 answers

#grammar context free
consider the following context-free language L:{[email protected]$^{R}$ is substing for x,where w,x$\epsilon (a+b)^{\ast }$} . which of follwoing CFG will reprsent above language : A) $S\rightarrow QP$ $P\rightarrow aPa|bQb|@Q$ $Q\rightarrow aQ|bQ|\epsilon$ B) $S\rightarrow PQ$ $P\rightarrow aPa|bQb|@Q$ $Q\rightarrow aQ|bQ|\epsilon$ C) both a and b D) none of these

asked Nov 28 in Theory of Computation by amit166 (113 points) | 9 views

0 votes

1 answer

Pumping Lemma TOC

answered Nov 27 in Theory of Computation by Mk Utkarsh (302 points) | 48 views

0 votes

0 answers

ace test series-toc1
anyone explain this concept? [closed]

asked Nov 26 in Theory of Computation by Rajesh Panwar (40 points) | 12 views

0 votes

0 answers

ACE Test Series TOC

asked Nov 26 in Theory of Computation by Rajesh Panwar (40 points) | 9 views

0 votes

0 answers

ACE Test Series TOC Test 57
I am getting A but answer is given as B. How to solve this. Thank you.

asked Nov 26 in Theory of Computation by DukeThunders (288 points) | 14 views

0 votes

1 answer

Rice Theorem
I am not able to understand Rice theorem. Can anyone suggest any reference where Rice theorem is explained properly with proper understandable explanation? Thank you

answered Nov 25 in Theory of Computation by Sathuri Bharath (71 points) | 25 views

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

Recent questions and answers in Theory of Computation

2,317 questions

1,295 answers

6,602 comments

89,719 users