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

+1 vote

0 answers

Theory of computation - Pumping Lemma for CFL [Self Doubt]

asked 3 days ago in Theory of Computation by hari0943 (9 points) | 10 views

0 votes

0 answers

Design Turing Machine for LANGUAGE L1=a*bb(a+b)*

asked May 6 in Theory of Computation by chris gyle (5 points) | 9 views

+1 vote

0 answers

Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.

asked May 3 in Theory of Computation by Setsu (13 points) | 9 views

+1 vote

0 answers

Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb. [closed]

asked May 3 in Theory of Computation by Setsu (13 points) | 6 views

0 votes

0 answers

PhD Admissions Written Test (Basic)
For any language L, and for any k ≥ 0, let L k denote the language obtained by concatenating any k strings from L (note that L^0 = epsilon). Suppose L1 is a context-free language and R is a regular language over the same alphabet Σ of size at least 3. The smallest value of k for which (R \ L1) k ∪ (L1 \ R) is not necessarily context-free is

asked May 2 in Theory of Computation by Rashimdixit (9 points) | 3 views

0 votes

0 answers

Ullman,rozen
Levi Ackerman: Is L= {xwywr∣x, w,y∈(a+b) +} regular? wr is reverse of w

asked May 2 in Theory of Computation by Gogo6996 (5 points) | 5 views

0 votes

0 answers

Ambiguity in grammar
Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.

asked May 2 in Theory of Computation by Sravanth0989 (5 points) | 3 views

0 votes

0 answers

Ambiguity of grammar
Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.

asked May 2 in Theory of Computation by Sravanth0989 (5 points) | 3 views

0 votes

0 answers

DFA construction
For E={a,b} construct a dfa for language L where L={w | w has a b in its 2nd last position if such a position exists}????

asked May 2 in Theory of Computation by harshit_1010 (5 points) | 3 views

0 votes

0 answers

madeeasys toc workbook
can somebody explain how to solve this type of questions

asked Apr 26 in Theory of Computation by jainanmol123 (13 points) | 18 views

0 votes

1 answer

Book: Introduction to formal languages and automata by Peter Linz----Chapter 2: Finite Automata----Exercises

answered Apr 21 in Theory of Computation by Konan-kun (71 points) | 29 views

0 votes

0 answers

#DFA Introduction, Formal Languages, DFA Construction examples

asked Apr 10 in Theory of Computation by DarkShadow18 (5 points) | 18 views

0 votes

0 answers

AppliedGate lecture example
What is the NFA that does not accept strings ending “101” ?

asked Apr 7 in Theory of Computation by shri385 (5 points) | 16 views

0 votes

0 answers

complement(ww) |w ε {a,b)* is CFL or Not
complement(ww) |w ε {a,b)* is CFL . BUt its Complement {ww|w ε {a,b}*} is not CFL ?HOW?

asked Apr 7 in Theory of Computation by diptanshu malviya (5 points) | 21 views

+1 vote

1 answer

#Toc #Applied
For this type of question, how did you attempt to make the DFA?

answered Mar 22 in Theory of Computation by zxy123 (3.6k points) | 24 views

0 votes

0 answers

Peter Linz An Introduction to Formal Languages and Automata 6th edition chapter 1.3 exercise 12

asked Mar 17 in Theory of Computation by cherryred1 (5 points) | 23 views

0 votes

0 answers

assignment for b.tech
Design turing machine that accepts all string containing at least one ‘a’ and ‘b’ where $\sum =(a,b,c)$

asked Mar 12 in Theory of Computation by amit166 (87 points) | 24 views

0 votes

1 answer

SELF DOUBT : What is the minimum DFA for (aa+aaa)* ?

answered Mar 7 in Theory of Computation by ascend (5 points) | 27 views

0 votes

0 answers

PDA for a^nb^n/n>=1
Is this PDA correct for a^n. B^n/n>=1?

asked Mar 4 in Theory of Computation by jaswanth431 (5 points) | 20 views

+2 votes

1 answer

Self Doubt on Theory of Computation
What is the intersection of recursive and recursively enumerable language?

answered Mar 4 in Theory of Computation by zxy123 (3.6k points) | 30 views

+1 vote

1 answer

Unambiguous Grammar
I am no able to prove if the following grammar is ambiguous. G=({S,A,B},{A,B},P,S} P: S->aAB|bBA A->bS|a B->aS|b Can some one help me prove it?

answered Mar 2 in Theory of Computation by zxy123 (3.6k points) | 33 views

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) | 32 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) | 44 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) | 48 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) | 18 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) | 25 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) | 34 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 (15 points) | 39 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) | 30 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) | 32 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) | 36 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) | 31 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) | 36 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) | 27 views

0 votes

0 answers

Madeeasy Test series TOC Q1

asked Jan 23 in Theory of Computation by Shivateja MST (45 points) | 22 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.6k points) | 40 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.6k points) | 35 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) | 24 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) | 21 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 (15 points) | 10 views

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

Recent questions and answers in Theory of Computation

9,270 questions

3,204 answers

14,751 comments

96,304 users