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

0 votes

0 answers

ACE Test Series
What is the minimum no of states in DFA which accepts the language generated by reg exp (0*1)*1(0+1)* ?. Is this binary strings containing 1? Pls Answer.

asked Feb 9 in Theory of Computation by akashks (5 points) | 26 views

0 votes

1 answer

Context Free Languages (Self Doubt)
I understand that the language L = {a^m b^n c^k|(m=n)or(n=k)} is CFL because it can be represented as the union of L1 = {a^m b^m c^k} and L2 = {a^m b^k c^k} which are both CFL's. But I can't figure out the working of the PDA accepting L. To check ... meaning (m=n) or (m-n) a's or (n-m) b's will remain in the stack meaning (m!=n). How can we check for (n=k) now?

answered Feb 7 in Theory of Computation by Ollie (525 points) | 37 views

0 votes

0 answers

Made easy test series
Consider the following problems and select the problem which is recursively enumerable but not recursive. (MSQ type) 1 . Whether a given Turing machine accepts non-empty language. 2. Whether a given Turing machine accepts finite language . 3. Whether a given Turing machine accepts at most 10 strings 4. Whether a given Turing machine accepts at least 10 strings.

asked Feb 4 in Theory of Computation by gajendercse (41 points) | 44 views

0 votes

0 answers

Practise Question from Ulman
Please give the DFA and regular expression

asked Feb 4 in Theory of Computation by chandra sai (5 points) | 11 views

0 votes

0 answers

made easy test series
Answer given is “All of these” My answer is none of these are regular.

asked Feb 3 in Theory of Computation by rahul65 (5 points) | 19 views

0 votes

0 answers

ACE Test Series
$A. Regular$ $B. CSL but not CFL$ $C. CFL$ $D. CSL$ Solution given is [closed]

asked Feb 2 in Theory of Computation by Parth27 (163 points) | 21 views

0 votes

0 answers

TOC Made easy
Consider the grammar consisting of seven productions. S → aA | aBB A → aaA | λ B → bB | bbC C → B After elimination of unit, useless, and λ -productions how many productions remain in the resulting grammar ? 2 3 4 5

asked Feb 2 in Theory of Computation by kirtipurohit (7 points) | 19 views

0 votes

0 answers

TOC | CSL Complement | Ace Pre Gate Question
The complemment of the language {wwww|w is in ([email protected]+$)*} is Regular CSL but not CFL CFL CSL Answer Can someone please explain how this language is CFL ?

asked Feb 1 in Theory of Computation by Sam_Gate21 (5 points) | 27 views

0 votes

0 answers

Gate Overflow itself
Is the explanation is correct? Link-https://gateoverflow.in/33183/complement-of-csl If I say complement of $a^{n}b^{n}c^{n} \, \, \, \, \, \, is\, \, \, \, \, a^{n}b^{n}c^{m} \: \: and\: \: \: m\neq n$ Then How Can it be regular?

asked Feb 1 in Theory of Computation by RavGopal (145 points) | 23 views

+1 vote

1 answer

Output Of Turing Machine : Ace Academy Subject Wise Test Series

answered Feb 1 in Theory of Computation by Parth27 (163 points) | 27 views

0 votes

0 answers

self doubt - decidability
L={<M>| M is a TM that accepts all even numbers}. How to check whether it is RE, REC or not RE… I think Rice’s theorem 2nd part is not applicable here

asked Feb 1 in Theory of Computation by Abhineet Singh (23 points) | 21 views

+1 vote

0 answers

Recursive Languages Self Doubt
Is recursive language closed under positive closure?

asked Jan 29 in Theory of Computation by aditi19 (53 points) | 23 views

+1 vote

1 answer

Applied AI ALL INDIA MOCK TEST
In option b, it can generate any string where a can be followed by b & then c or b followed by a & then c , c by a & then b i.e sequence od characters isn’t fixed. Does it have a CFG for it?

answered Jan 25 in Theory of Computation by Sahil91 (683 points) | 20 views

0 votes

0 answers

Madeeasy Test series TOC Q1

asked Jan 23 in Theory of Computation by Shivateja MST (45 points) | 10 views

+1 vote

1 answer

Peter Linz Ex-7.3 Q6 CFL
L=$a^nb^{2n} | n\geq 0$ is a DCFL. Show that L* is DCFL

answered Jan 23 in Theory of Computation by zxy123 (3.2k points) | 26 views

+1 vote

1 answer

Made easy test series
Can anyone draw the DFA’s for the question mentioned?

answered Jan 22 in Theory of Computation by zxy123 (3.2k points) | 32 views

0 votes

0 answers

CFG Self-doubt
As per the definition of CNF and GNF, these grammars doesn’t allows $\epsilon$ productions. What if the language contains $\epsilon$? In that case how do we convert the CFG to CNF and GNF? Can someone explain with an example?

asked Jan 20 in Theory of Computation by aditi19 (53 points) | 18 views

0 votes

1 answer

Show that the language S-> aSS| b is not regular ?

answered Jan 20 in Theory of Computation by SarathBaswa (849 points) | 19 views

0 votes

0 answers

An introduction to formal languages and automata
How can I explain that this language- L= { a<sup>n</sup> b<sup>l</sup> : n ≠ l } is not regular. [USE PUMPING LEMMA OR CLOSURE PROPERTIES] This question is under a book named An introduction to ... understandable manner and show how you exactly arrived at the solution? That would be a great help to me. Thanks in advance

asked Jan 18 in Theory of Computation by kirtipurohit (7 points) | 9 views

0 votes

1 answer

Does Left recursive grammar same as left linear grammar

answered Jan 17 in Theory of Computation by wander (301 points) | 14 views

0 votes

0 answers

An introduction to formal languages and automata peter linz

asked Jan 16 in Theory of Computation by kirtipurohit (7 points) | 26 views

0 votes

0 answers

Peter Linz 5e Ex-2.1 Q-7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ } [closed]

asked Jan 14 in Theory of Computation by aditi19 (53 points) | 10 views

+1 vote

0 answers

Peter Linz 5e Ex-2.1 Q7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }

asked Jan 14 in Theory of Computation by aditi19 (53 points) | 29 views

0 votes

1 answer

Ace test series
[closed]

answered Jan 7 in Theory of Computation by Abhisheksmile94 (347 points) | 35 views

0 votes

0 answers

Ace Test Series
Is C Valid Answer? I feel regular expression in C can also Generate 11 which is not there in language so the answer should be D only….Is my reasoning valid if not please help to clear this concept...

asked Jan 6 in Theory of Computation by vipin.gautam1906 (9 points) | 37 views

0 votes

0 answers

Self doubt on decidability of turing machine and dfa

asked Jan 5 in Theory of Computation by meivinay (5 points) | 58 views

0 votes

1 answer

Applied Test Series TOC
Options: My answer was: D answer according to them was B and D and their explaination was

answered Jan 4 in Theory of Computation by Abhisheksmile94 (347 points) | 28 views

0 votes

0 answers

GATE 2003 , Theory Of Computation , Turing Machine

asked Jan 4 in Theory of Computation by Pushkar Khadase (5 points) | 29 views

0 votes

1 answer

Theory of automata
Convert the Following DFA to Regular Expression using GNFA.

answered Jan 3 in Theory of Computation by Abhisheksmile94 (347 points) | 42 views

0 votes

2 answers

TOC- closure properties of RL
let L1=a^n (which is a regular language) and L2=b^n (which is also a regular language) L1.L2 is also regular.. how?? as (a^nb^n) is not a regular language

answered Jan 3 in Theory of Computation by Abhisheksmile94 (347 points) | 49 views

0 votes

3 answers

youtube exercise unacademy
L1=a^n,,n>0 L2=a^n b^n c^n , n>0 L1.L2 is a)regular b)cfl c)csl d)none

answered Jan 3 in Theory of Computation by Abhisheksmile94 (347 points) | 44 views

0 votes

0 answers

My college homework
1) Let ∑ = {D , L}. Find a DFA that accepts Password (P) with the following conditions: - | P | ≥ 4 - P begins with a letter and ends with a letter. - P contains at least one digit. 2) Let ∑ = { 0..9 , ... the following DFA that has access to the laboratories of company controlled. The employee number becomes read as a binary number. Which employee numbers are accepted.

asked Dec 29, 2020 in Theory of Computation by MotasemMobayyed (5 points) | 11 views

0 votes

1 answer

KLP MISHRA #TOC #Precedence of operators #computaion

answered Dec 23, 2020 in Theory of Computation by Harshal Vora (11 points) | 14 views

0 votes

0 answers

lIntroduction to Languages and The Theory of Computation

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 12 views

0 votes

0 answers

Introduction to Languages and The Theory of Computation

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 6 views

0 votes

0 answers

Introduction to Languages and The Theory of Computation John C. Martin North Dakota State University

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 9 views

0 votes

0 answers

John C. Martin 4.9
4.9. Suppose that G1 = (V1, {a, b}, S1, P1) and G2 = (V2, {a, b}, S2, P2) are CFGs and that V1 ∩ V2 = ∅. a. It is easy to see that no matter what G1 and G2 are, the CFG Gu = (Vu, {a, b}, Su, Pu) defined by Vu = V1 ∪ V2, Su = S1, and Pu = P1 ∪ ... {S1 → S1S1 | } generates every string in L(G1) ∗. Find a grammar G1 with V1 = {S1} and a string x ∈ L(G ∗ ) such that x /∈ L(G) ∗.

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 7 views

0 votes

0 answers

Introduction to Languages and The Theory of Computation John C. Martin

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 8 views

0 votes

1 answer

This was asked in ace academy test series, but no suitable explaination was provided. Kindly enlighten!

answered Dec 22, 2020 in Theory of Computation by Deepakk Poonia (Dee) (1.5k points) | 35 views

0 votes

1 answer

#selfdoubt #regular_toc_languages

answered Dec 21, 2020 in Theory of Computation by Sahil91 (683 points) | 26 views

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

Recent questions and answers in Theory of Computation

9,095 questions

3,154 answers

14,583 comments

95,939 users