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

0 votes

2 answers

theory of computation
hi guys, I have a doubt- if two DFA accept the same set of language then are they equal? why or why not? answer really appreciated

answered 3 days ago in Theory of Computation by shweta._.5 (71 points) | 40 views

0 votes

0 answers

Self Doubts..
What would be the minimum number of states in a DFA on {a,b} where number of a's is divisible by 2 OR number of b's divisible by 3?

asked Oct 23 in Theory of Computation by Sinchit (15 points) | 39 views

0 votes

0 answers

Testbook.com Test Series
Let L, M be any two Context Free Languages and X be a Regular Language. Which of the following statements given below are always correct ? A.) M – X is Context Free. B.) L $\cap$ M is Regular Language. C.) L $\cup$ M is Context Free. D.) M – X is Context Sensitive Language.

asked Oct 22 in Theory of Computation by Rishav Chetan (5 points) | 14 views

0 votes

2 answers

Self Doubt: Topic Name- Decidability
L = { <M>| L(M) Contains at least 21 members} Where M = Turing machine Is this language Undecidable and if so how?

answered Oct 22 in Theory of Computation by spike500 (17 points) | 25 views

0 votes

0 answers

Gate Overflow Test
gate-overflow-test:Deterministic-Pushdown-Automata accepting by empty stack accepts all Deterministic-Context-Free-Languages having prefix property. Regular languages having prefix property is a subset of Deterministic-Context-Free-Languages having prefix property. can anyone explain what actually that means.

asked Oct 22 in Theory of Computation by Vaibhav98 (5 points) | 20 views

0 votes

0 answers

Theory of computer science
regular language closed under intersection with any language true or false

asked Oct 20 in Theory of Computation by nihal singh parihar (5 points) | 26 views

0 votes

0 answers

Self Doubt in Theory of Computation, Regular Language

asked Oct 19 in Theory of Computation by nvs16 (9 points) | 47 views

0 votes

0 answers

Peter Linz 5th edition
Find grammars for the following languages on ∑ = {a}, L = {w : |w| mod 3 > 0}.

asked Oct 19 in Theory of Computation by PrinceSoni (5 points) | 8 views

0 votes

0 answers

https://www.tutorialspoint.com/automata_theory/undecidable_languages.htm

asked Oct 18 in Theory of Computation by killCode47 (5 points) | 11 views

0 votes

1 answer

GeeksforGeeks
The regular expression 0*(10*)* denotes the same set as (A) (1*0)*1* (B) 0 + (0 + 10)* (C) (0 + 1)* 10(0 + 1)* (D) none of these

answered Oct 11 in Theory of Computation by iarnav (231 points) | 26 views

0 votes

1 answer

Test series TOC question
Is L={uv / |u|=|v| & u ≠v & u,v ϵ {a,b}* } a CFL? If yes then can you design a PDA for it.

answered Oct 11 in Theory of Computation by iarnav (231 points) | 24 views

0 votes

0 answers

thoery of computation
What is the difference between cross product,concatenation or union in thoery of computation and when to use them?

asked Oct 9 in Theory of Computation by Musa (5 points) | 17 views

0 votes

1 answer

Finding number of equivalence class for a finite automata

answered Oct 9 in Theory of Computation by iarnav (231 points) | 33 views

0 votes

1 answer

GATEBOOK TEST SERIES - TM Q-4
Consider the following three statements. I. If the language L is recognized by a nondeterministic finite automaton, then L is recognized by a deterministic finite automaton. II. If the language L is recognized by a nondeterministic pushdown automaton, then L is ... (D) One of the three statements is known to be true; the other two statements are known to be false.

answered Oct 9 in Theory of Computation by iarnav (231 points) | 52 views

0 votes

1 answer

Design NFA (without ε moves) for the regular language that consist of all strings with at least two consecutive 0's

answered Oct 9 in Theory of Computation by spike500 (17 points) | 25 views

0 votes

1 answer

Construct regular expression for the language that consists of all strings ending with 00. Assume Σ= {0, 1}.

answered Oct 9 in Theory of Computation by spike500 (17 points) | 35 views

0 votes

0 answers

GATEBOOK TEST SERIES - TM
is a language and is a Turing machine which accepts . loops on epsilon forever. Which one of the following statements is true ? (A) is r.e but not recursive (B) can be non r.e (C) can not be recursive (D) can be regular

asked Oct 7 in Theory of Computation by Gate2022 (7 points) | 21 views

0 votes

1 answer

GATEBOOK - Test Series - TOC
Consider the following problems. 1. Given a TM M and a string w, does M ever write the symbol ... of the above problems are decidable? (A) Only 4 (B) 2 and 3 Only (C) 2 and 4 Only (D) 2, 3 and 4 Only

answered Oct 7 in Theory of Computation by g21 (1k points) | 21 views

0 votes

2 answers

GATEBOOK - Test Series - TOC
Consider the following statements S1: If F is a finite language and L is some language, and is a regular language, then L must be a regular language. S2: If A is regular and is regular then so is B. Which one of the following statements is True ? (A) Only S1 (B) Only S2 (C) Both S1 and S2 (D) Neither S1 or S2

answered Oct 7 in Theory of Computation by g21 (1k points) | 92 views

0 votes

1 answer

madeeasy topicwise
C = {x | x is a binary string and decimal of any prefix of x is not of the form 3m+2 , where m>=0 } Is ir true or false ? The sol is given as true but I am getting it false plz correct.

answered Oct 7 in Theory of Computation by Arkaprava (711 points) | 40 views

0 votes

1 answer

self doubt toc
(0+1)*01(0+1)* + 1*0* = (0+1)* How is this regular expression equivalent to expression at rhs ? As ,at rhs we can get epsilon but in lhs we cant get epsilon ...

answered Oct 6 in Theory of Computation by Shashank Rustagi (513 points) | 40 views

0 votes

0 answers

GATEBOOK Test Series - TOC
Let h be the homomorphism defined by h(a) = b and h(b) = a. Let Which of the following statements is correct? (A). L is regular. (B). L is non regular DCFL (C). L is non-DCFL But CFL (D). L is Non-CFL

asked Oct 2 in Theory of Computation by Gate2022 (7 points) | 20 views

0 votes

0 answers

GATEBOOK Test Series - Closure Properties
Consider the following statements : 1. if a deterministic finite automaton M over alphabet accepts all strings of length less than or equal to the number of states in M, then it must accept all strings over . 2. if a non-deterministic finite automaton M over alphabet ... of the above statements is/are correct ? A. Only 3 B. Only 1,3,4 C. Only 1,2,3 D. ALL

asked Oct 2 in Theory of Computation by Gate2022 (7 points) | 19 views

0 votes

0 answers

GATEBOOK - Test Series - TOC
Consider the CFG 'G' given below ,where S and A are non-terminals, S is the start symbol, and {0,1} is the set of terminals. Let L(G) denote the language generated by the above grammar, language L(G) is (A) Regular (B) DCFL but not Regular (C) CFL but not DCFL (D) CSL but not CFL

asked Oct 2 in Theory of Computation by Gate2022 (7 points) | 12 views

0 votes

0 answers

Self Doubt Theory of Computation-How to distinguish when to use cross product, concatenation or Union in DFA?

asked Oct 2 in Theory of Computation by the_dalela (5 points) | 8 views

0 votes

0 answers

#TOC SELF DOUBT ISI 2014
L IS SUBSET OF {A,B}* AND If L* is regular, then is L regular? JUSTIFY YOUR ANSWER.

asked Oct 2 in Theory of Computation by iarnav (231 points) | 8 views

0 votes

0 answers

TOC self doubt
L={ a^m b^n | m,n>=0} We know above language is regular as it doesn’t need any comparisons…. But Here L={ϵ, a,b,abb,aab,aabbb………...} If we take aabbb and if we apply Pumping Lemma by taken u=a, v=ab and w=bb let i=1 then we get aababbb which will not be in given language then how come it is regular? Where am i going wrong?

asked Sep 30 in Theory of Computation by Pathki Shivamsh (9 points) | 15 views

0 votes

2 answers

Applied test series
Minimum number of States in a DFA , that accepts all strings of 0s and 1s ,whose integer equivalent are not divisible by 2 OR 3

answered Sep 29 in Theory of Computation by iarnav (231 points) | 53 views

0 votes

2 answers

Ace academy test series

answered Sep 29 in Theory of Computation by iarnav (231 points) | 51 views

0 votes

0 answers

#TOC Whether give languages are DCFL or just CFL?
Please explain for all these 4 languages about which of them are DCFL and which are just CFL only? Thank you.

asked Sep 29 in Theory of Computation by iarnav (231 points) | 8 views

0 votes

0 answers

TOC self doubt
How to prove L={a ^n^2:n≥0} is not context free using Pumping Lemma?

asked Sep 28 in Theory of Computation by Pathki Shivamsh (9 points) | 13 views

0 votes

0 answers

TOC Self Doubt
L1= a^n b^n| n>=0 L2=ww^r | w ϵ (a+b)* what will be the prefix(L1),Suffix(L1) and prefix(L2),Suffix(L2) ??? Please Explain in detail

asked Sep 26 in Theory of Computation by Pathki Shivamsh (9 points) | 20 views

0 votes

0 answers

# MadeEasy test

asked Sep 26 in Theory of Computation by raviranjan21 (5 points) | 23 views

0 votes

1 answer

Self Doubt - ME Notes (TOC)
Construct the minimal DFA for the following $\epsilon$ NFA NOTE: No need to give a complete explanation. Just provide me the final answer whatever you are getting means the number of states and the name of the states.

answered Sep 22 in Theory of Computation by Ehraz Hasan (366 points) | 31 views

0 votes

0 answers

properties of regular language
Question let Σ = {1, 2}, Let L1 = {1^n 2^m 1^n+m | n ≥ 0, m ≥ 0}. show that L1 is not a regular language. Proof: Assume L1 is regular. We know that language L2 = {2^n1^n | n ≥ 0} is not a regular ... expression 2*1*. Since regular languages are closed under intersection, Hence L1 is not regular. is the above proof correct if not what modification i need to do

asked Sep 21 in Theory of Computation by prince123 (5 points) | 20 views

0 votes

0 answers

Theory-of-Computation PDA (Self Doubt)
Can we construct PDA for the given Language: L = {a^i b^j c^k d^l } where i = k, j = l

asked Sep 20 in Theory of Computation by iot_ts (5 points) | 24 views

0 votes

0 answers

made easy test series
Answer to the above question is incorrect I think can anyone please confirm it? Explanation given is incorrect

asked Sep 19 in Theory of Computation by Nishinoya (5 points) | 36 views

0 votes

0 answers

Peter Linz Ex- 8.1
https://gateoverflow.in/123323/peter-linz-exercise-8-1 Can someone help me with this question? It is CFL or not?

asked Sep 18 in Theory of Computation by Ehraz Hasan (366 points) | 27 views

0 votes

0 answers

#toc#zeal test series #cfl
Why 3 language is a CFL,please explain?

asked Sep 18 in Theory of Computation by Syywyeye (5 points) | 29 views

0 votes

0 answers

made easy test series
if L1 is regular and L2 is DCFL then (L1 intersection L2*)’ is what a)CFL b)CSL c)recursive d)REL options given are b,c,d but if we apply * to any language it becomes regular language then (regular intersection regular) is regular so option should be “all are correct”. Can any one please explain?

asked Sep 18 in Theory of Computation by arnavd83 (5 points) | 29 views

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

Recent questions and answers in Theory of Computation

8,438 questions

2,715 answers

13,242 comments

95,460 users