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

0 votes

3 answers

Self doubt TOC
What is the regular expression for this given DFA?

answered 6 hours ago in Theory of Computation by shaktisingh (27 points) | 53 views

0 votes

0 answers

Is this a Regular language or not?
Here ‘w^r’ is the reverse of string ‘w’.

asked 3 days ago in Theory of Computation by luc_Bloodstone (11 points) | 14 views

0 votes

0 answers

MADE EASY TOC 2020
L1 CSL, L2 CFL L1 CSL, L2 CSL L1 CFL, L2 CFL L1 CFL, L2 CSL

asked 4 days ago in Theory of Computation by Debapaul (117 points) | 16 views

0 votes

0 answers

Self Doub in finding the substring.
The number of substrings of length $\le3$ generated by the regular expression $\mathrm {(a+ba)^*b(a+b)^*}$ is___________________. I am getting $15$ as the answer.

asked Oct 13 in Theory of Computation by `JEET (155 points) | 13 views

0 votes

1 answer

Ace booklet question on dfa
The minimal finite automata for the set of all strings over $(0+1+2)^*$ that interpreted as integer representation of a base 3 number as congruent to 5 modulo 6 has a) 5 b) 6 c) 7 d) none I am getting $6$ but the answer given is none of these.

answered Oct 12 in Theory of Computation by Verma Ashish (262 points) | 31 views

0 votes

1 answer

TOC Ace Academy Topicwise
My approach was: F is finite language so it will definitely be Regular Language and thus L is the set of all Regular languages. Since Regular languages are closed under every property given in the option so I marked the answer as None of these But the ... is ( C ) complement. Let me know, if my approach to solve the question is wrong. Also Explain the correct answer.

answered Oct 10 in Theory of Computation by Satbir (2.5k points) | 24 views

0 votes

1 answer

Self doubt regarding pda
Design a PDA for this language – {$a^{i}b^{j}c^{k}$ | if i=j then k is even}

answered Oct 10 in Theory of Computation by Satbir (2.5k points) | 10 views

0 votes

0 answers

ACE Topicwise test TOC
I thought, the answer is Recursively Enumerable language but the answer is given as Regular language. Please Explain?

asked Oct 10 in Theory of Computation by Rudr Pawan (577 points) | 14 views

+1 vote

0 answers

Peter Linz-TOC
What are these languages among them: Regular, DCFL, CFL, CSL, REC, RE ? $L1=(w_{1}w_{2}: w_{1}\neq w_{2}: |w_{1}|=|w_{2}| )$ $L2=(a^nb^m: m=n^2,n\geqslant 1 )$ $\\L3=(w^n : w\epsilon (a,b)^+,n\geqslant 2)\\ L4=(www^R: w\epsilon (a,b)^+)$ $L5=(wuw^R: w,u \ \epsilon (a,b)^+, |w|\geqslant |u|)$ $L6=(a^nb^ma^{nm}: n\geqslant 1,m\geqslant 1)$

asked Oct 6 in Theory of Computation by Kushagra गुप्ता (82 points) | 19 views

0 votes

0 answers

Made Easy Test Series 2020
Consider the language L: $L=\{ <M>| M $ is a turing machine and $L(M) \leq_p {0^p1^{2p} | p > 0} $ $ \} $ Where the symbol $``\leq_p”$ refers to polynomial time reduction then $L$ is decidable or undecidable $???$

asked Oct 3 in Theory of Computation by Optimus Prime (6 points) | 10 views

0 votes

0 answers

peter-linz-edition-4-exercise-4.3-question-3,4,5-page-no-122(Modified)

asked Oct 3 in Theory of Computation by Kushagra गुप्ता (82 points) | 14 views

0 votes

0 answers

Testbook Test Series-TOC
$\\ L_{1}= (0^m1^m0^n | m,n>0) \ \ \ \ \ L_{2}=(0^m1^n0^n |m,n>0)\\ L_{1}\cup L_{2} \ ?\\ \\ 1. Dcfl\\ 2. Cfl\\ 3.Unambiguous\\ 4.Inherently \ ambiguous$ Answer given as 2 and 4 and I am facing difficulty to understand the 4th option. Please if any idea to anyone, do tell.

asked Oct 2 in Theory of Computation by Kushagra गुप्ता (82 points) | 53 views

0 votes

1 answer

Geeks for Geeks Mock
Consider the following context-free grammar over the alphabet ∑ = {a, b} with S as the start symbol: S → AT A → aAa | bAb | #T T → aT | bT | λ Which of the following represents the language generated by the above grammar? A { w#x | w^R is a substring of x, where ... | w, x ∈ {a, b}* } What Should be the answer I'm getting B as answer but at GFG website it is mentioned as A????

answered Oct 1 in Theory of Computation by Shaik Masthan (227 points) | 21 views

0 votes

0 answers

Self thought: Deterministic Push Down Automata
Are the following language Deterministic PDA? $\text{1. L} = \{ a^nb^n | n \geq1\} \cup \{a^m \}$ $\text{2. L} = \{ a^nb^n | n \geq1\} \cup \{a^m | m \lt n\}$ $\text{3. L} = \{ a^nb^n | n \geq1\} \cup \{a^m | m \gt n\}$ $\text{4. L} = \{ a^nb^n | n \geq1\} \cup \{a^m | m = n\}$

asked Sep 30 in Theory of Computation by !KARAN (118 points) | 28 views

0 votes

0 answers

GradeUp Quiz ToC
Consider a grammar G A → AB AB → BC BC → CD CD → a The Language L generated by G is most accurately said to be Chomsky type 3 Chomsky type 2 Chomsky type 1 Chomsky type 0

asked Sep 27 in Theory of Computation by aditi19 (44 points) | 12 views

0 votes

0 answers

Peter Linz Edition 4 Exercise 2.1 Question 7-c,d,e,f (Page No. 47)

asked Sep 27 in Theory of Computation by Kushagra गुप्ता (82 points) | 19 views

0 votes

1 answer

#gatebook_test
T/F DFA with single final state has the same powers as DFA with more than one final state ans: given F i think its ture

answered Sep 26 in Theory of Computation by GAITONDE (1.2k points) | 12 views

+1 vote

1 answer

Self Doubt: PDA
My ans is all, but ans given is 1 only, why?

answered Sep 26 in Theory of Computation by Satbir (2.5k points) | 26 views

0 votes

1 answer

gatebook_testS29
Let which of the following is true about ? (A) L is CFL but not DCFL (B) L is regular but not CFL (C) L is DCFL but not regular (D) None of these

answered Sep 26 in Theory of Computation by Satbir (2.5k points) | 30 views

0 votes

0 answers

gatebook_test_20
L is a language defined over alphabet . There is a one to one correspondence between L and Natural numbers N. P. is regular but not context free Q. is context free but not recursive R. is recursively enumerable but not recursive S. is finite Which of the following could be true about L ? (A) Only P (B) Only P, Q (C) Only P, Q and R (D) All of P,Q,R,S [closed]

asked Sep 25 in Theory of Computation by mohan123 (20 points) | 11 views

0 votes

0 answers

MADE EASY test-series 2020
$(A) L = \{a^mb^nc^k | if (m\space is\space even)\space then\space n=k \}$ $(B) L = \{a^mb^nc^k | if (n\space is\space even)\space then\space m=k \}$ ... . So, if m is odd then we should accept any combination of $n$ and $k$(in perticular n=1, k=0 should be accepted). What should be the correct answer.

asked Sep 25 in Theory of Computation by Vimal Patel (217 points) | 13 views

0 votes

0 answers

#theory of computation
Set of all strings over Σ={a,b} in which (1) every 'a' must not followed by b. (2) 'a' is not followed by b. Are these (1) and (2) same ?? #TOC

asked Sep 21 in Theory of Computation by IamSuraj (6 points) | 42 views

0 votes

0 answers

Self doubt in TOC
We know that kleene closure of cfl is cfl. L = {w c w^r x | w,x € {a,b}* } is cfl.how its kleene closure is cfl?

asked Sep 21 in Theory of Computation by aditya059 (45 points) | 23 views

+1 vote

4 answers

Zeal question book
The language containing the set of stings over alphabet {0,1,2} where the number of 1s equals the numbar of 2s and every 0 is followed immediately by at least three 1 is: (1)Regular (2)Non Deterministic Context Free (3) Deterministic Context Free (4) Recursive

answered Sep 21 in Theory of Computation by Vimal Patel (217 points) | 62 views

0 votes

1 answer

Most number of configurations of a Turing Machine
Let m be the number of states in a turing machine M, and k be the size of the alphabet that M uses, and if M uses at most r squares of its tape, then there are at most m.r.k^r configurations please prove it..or explain it...

answered Sep 21 in Theory of Computation by BLACK_CLOUD (14 points) | 10 views

0 votes

1 answer

gatebook_2020_test
For instance, the grammar G with , P with start symbol S and rules Which of the following is true about L(G) ? (A) It is a regular language as G is a regular grammar (B) It is a non regular language as G is not a regular grammar (C) It is a non regular and G is a non-regular grammar (D) It is a regular language and G is not a regular grammar

answered Sep 20 in Theory of Computation by Bikram (1.2k points) | 14 views

0 votes

1 answer

selg doubt regarding PDA
Suppose I’ve two pda, PDA accepts string by empty stack = $M_{1}$ PDA accepts string by final state = $M_{2}$ Now I can’t detect the reason why , In case of NPDA, $L(M_{1})$ = $L(M_{2})$ but incase of DPDA, $L(M_{1})\subset L(M_{2})$ please give me the explanation.

answered Sep 19 in Theory of Computation by Bikram (1.2k points) | 23 views

0 votes

2 answers

SELF - DOUBT
L=a language M= a TM Lc= complement of L 1) L={<M> | M is a TM, encoded with some alphabet } ; L is recursive 2) L=set of all cfls generated by some cfg; => L is recursive enumerable but not recursive , Lc is ... is Recursively Enumerable but Not Recursive I BELIEVE THE ABOVE STATEMENTS TO BE TRUE / CORRECT please somebody verify and reply please do reply ASAP THANKING YOU.

answered Sep 19 in Theory of Computation by Bikram (1.2k points) | 15 views

0 votes

0 answers

Zeal question book
The language (0^m 10^m!) is: (a)Regular (c) Nondeterministic Context Free (b) Deterministic Context Free (d) Recursive.

asked Sep 17 in Theory of Computation by vijay kumar 2 (9 points) | 13 views

0 votes

0 answers

selfdoubt - What is the order in which the following set of actions must be performed on a CFG?

asked Sep 16 in Theory of Computation by commenter commenter (30 points) | 14 views

0 votes

0 answers

self_doubt..
question: L={<m>| m is a TM} alphabet={0,1} is L recursive? we know L is countable infinity.. and also not all possible strings in alphabet is a TM. so if L is recursive it should have a decider…

asked Sep 16 in Theory of Computation by BLACK_CLOUD (14 points) | 8 views

0 votes

0 answers

madeeasy 2018-'18 session
$S=aSb|aSbb|aSbbb|aSbbbb|....|\epsilon $ S..non terminal $a,b,\epsilon$..terminal $\epsilon$.. epsilon (empty string) whats the language? i suppose.. $\epsilon$ in language ab,abb,abbb,abbbb....in Language aabb,aabbb,aabbbb,aabbbbb...in language aaabbb,aaabbbb,aaabbbbb....in ... so it is a DCFL.. PLEASE CORRECT ME IF I'M WRONG.

asked Sep 16 in Theory of Computation by BLACK_CLOUD (14 points) | 6 views

+1 vote

1 answer

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

answered Sep 16 in Theory of Computation by Shaik Masthan (227 points) | 35 views

0 votes

2 answers

undecidability- the gatebook test series
L = {<M>| M is a TM and |L(M) |<= 3} . RE or not RE .

answered Sep 14 in Theory of Computation by Bikram (1.2k points) | 20 views

0 votes

0 answers

madeeasy-2018-'19 session
{<M> | M accepts at least 2 strings of different length} is it R.E language? with rice's theorem 1..i can say its undecidable as its certainly non-trivial i can say its not non-monotonic as all so proper supersets has this property.so theorem 2 is ... what type of language is it? R.E. is the probable ans.. but how to know for sure?? any intuitive proof..?? thanks

asked Sep 14 in Theory of Computation by blackcloud (6 points) | 7 views

0 votes

0 answers

Whether a TM accepts a Recursively enumarable language. Decidable or not ?

asked Sep 14 in Theory of Computation by Amal (23 points) | 17 views

0 votes

0 answers

From the "Suggested Exercises" section(at the end of the book) of "Principles of Compiler Design" By Aho and Ullman.

asked Sep 12 in Theory of Computation by Sukhbir Singh (8 points) | 14 views

0 votes

1 answer

what is the regular expression for the language? [Gate Academy TOC Topic Test Finite automata]

answered Sep 12 in Theory of Computation by sanju77767 (10 points) | 21 views

0 votes

1 answer

Whether following language is linear or not?
I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$. Now, I wanted to determine whether this language is linear or not. So, I came up with this grammar: $S \rightarrow A\thinspace|\thinspace Sc$ ... So, I'm unable to find whether the language is linear or not and what goes wrong in above logic with either case. Please help.

answered Sep 12 in Theory of Computation by Bikram (1.2k points) | 12 views

0 votes

4 answers

what is the regular expression for the complement of the language? [Gate Academy TOC Topic Test Finite automata]

answered Sep 12 in Theory of Computation by Bikram (1.2k points) | 14 views

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

Recent questions and answers in Theory of Computation

1,674 questions

1,085 answers

4,521 comments

89,591 users