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

0 votes

0 answers

NIELIT Scientist B 2016
Which of the following is wrong: A. Turing machine is a simple mathematical model of general purpose computer B. Turing machine is more powerful than finite automata C. Turing machine can be simulated by a general purpose computer D. All of the above ... are wrong. Turing machine is more powerful than finite automata is true, similarly option C and A also seems to be true.

asked 17 minutes ago in Theory of Computation by Ollie (6 points) | 2 views

0 votes

0 answers

what is the Meaning of following in peter linz algortihm for Chapter 3 , Nfa to Rex?

asked 1 day ago in Theory of Computation by lokopi (6 points) | 8 views

0 votes

0 answers

Self Doubt 5:Peter Linz(exercise 1.2)
$L1={a^{n} b^{m};n>=0,m<n}$ $L2={a^{n} b^{(n-2)};n>=3}$ $L3=complement$ $of$ $L2.$ $L1-L3$ is? According to me $L1-L3$ is same as $L2$. Please verify.

asked 1 day ago in Theory of Computation by Doraemon (100 points) | 14 views

0 votes

0 answers

TOC-Which of the following is true?
L1={a^n b^m:n>=0,m<n} L2={a^3n b^2n : n>2} L3={a^n b^m: m<=n-3 or m=n-1} i>L1 U L2 IS A DCFL ii>L1 L2 IS A DCFL iii>L3 is a DCFL. Please verify which of the following is true?

asked 1 day ago in Theory of Computation by Doraemon (100 points) | 5 views

0 votes

1 answer

self doubt 2-PDA
If suppose we have an NPDA for a language,Does that mean that the language is always NCFL?

answered 1 day ago in Theory of Computation by !KARAN (351 points) | 11 views

0 votes

1 answer

self doubt 4 -Peter Linz-chapter 7.
It has been told in Peter Linz that if L1 is deterministic context-free and L2 is regular, then a) the language L1 ∪ L2 is deterministic context-free b) the language L1 ∩ L2 is deterministic context-free. But DCFL is not closed under ... regular language is a DCFL then automatically , therefore L1UL2 and L1 ∩ L2 might not be closed. Can anyone please verify?

answered 2 days ago in Theory of Computation by !KARAN (351 points) | 12 views

0 votes

0 answers

SELF DOUBT-3(PDA)
Can someone give me the PDA for this language? L={W BELONGS TO {a+b+c}*; (no. of a+no. of b) not equal to the number of c} Actuallly I am getting a NPDA for this .does this language have a DPDA?

asked 3 days ago in Theory of Computation by Doraemon (100 points) | 5 views

0 votes

0 answers

REQUEST FOR SOLTION MANUAL FOR PETER LINZ
Can anyone provide me with the solution manual for 6TH EDITION OF PETERLINZ.(or if not available any edition you have)

asked 3 days ago in Theory of Computation by Doraemon (100 points) | 4 views

0 votes

1 answer

TYPE OF THE LANGUAGE-Peter Linz -chapter 4
L={a^n:n is either prime or product of 2 or more prime numbers} According to me this is regular. Can anyone verify?

answered 5 days ago in Theory of Computation by Kushagra गुप्ता (261 points) | 20 views

0 votes

1 answer

self doubt on toc finit automata
What will be the number of states in minimal DFA, if every string contains aa and bb as substring ?

answered Mar 26 in Theory of Computation by !KARAN (351 points) | 20 views

0 votes

0 answers

Context free language self doubt २
Q. Consider the following context free language L = { w # x | w^r is a substring for x , where w, x € {a, b}^* } Which of the following CFG will represent the above language Option: A) S -> PQ P -> aPa | bPb | #Q Q -> aQ | bQ | € B) S -> QP P -> aPa | bPb | #Q Q -> aQ | bQ | € C) A and B D) None of the these

asked Mar 25 in Theory of Computation by Hradesh patel (7 points) | 6 views

0 votes

0 answers

https://nptel.ac.in/content/storage2/courses/downloads/106104148/Week_02_Assignment_02.pdf

asked Mar 21 in Theory of Computation by Vaishnav (6 points) | 28 views

0 votes

1 answer

GATE 2020 TOC
Given four languages, which of the following are undecidable? Where < M > denotes encoding of a Turing machine M L1 = {< M >|L(M) = ϕ} L2 = {< M, w, q >| M will visit the state q when M execute on w and take exactly 100 steps} L3 = ... (C) L1& L4 (D) L1, L3& L4 i am confused about option 3 as it is recursive so TM will either halt or not.give ur explanation.

answered Mar 19 in Theory of Computation by smsubham (64 points) | 20 views

0 votes

1 answer

Context free language doubt 1
Ravi considers two CFLs L1 and L2, performs the following operation on both the languages. (i) He unions L1 and L2 to obtain a new language L3 (ii) He concatenates L1 and L3 to obtain L4 (iii) He takes complement of L4 to obtain L5 The language L5 is a.REL but not Recursive b.Recursive but not CSL c.CFL but not CSL d.CSL

answered Mar 18 in Theory of Computation by smsubham (64 points) | 20 views

0 votes

1 answer

Gate 1992 Question
In which of the cases stated below is the following statement true? “For every non-deterministic machine M1, there exists an equivalent deterministic machine M2 recognizing the same language“. (a) M1 is a non-deterministic finite automaton (b) M1 is a non-deterministic PDA (c) M1 is a non-deterministic Turing machine (d) For no machine M1 use the above statement true

answered Mar 10 in Theory of Computation by Ram Swaroop (270 points) | 11 views

0 votes

1 answer

Regular Languages self doubt
What is the language given by this : ${\color{Red} {a^mb^n|LCM(m,n)<=1}}$

answered Mar 9 in Theory of Computation by !KARAN (351 points) | 13 views

0 votes

1 answer

Automata - DFA
In what cases we need to include epsilon in DFA.

answered Mar 2 in Theory of Computation by !KARAN (351 points) | 23 views

0 votes

0 answers

Made easy work book toc
Why aa*(bb*a)* not a regular expressian for starting and ending with symbol A Dfa

asked Feb 25 in Theory of Computation by Ritesh123 (6 points) | 15 views

0 votes

0 answers

regular expression self doubt
Given the regular expression L(ab*aa+bba*ab). in this question my doubt is what is the number of states in minimum nfa and minimum dfa for this expression.

asked Feb 17 in Theory of Computation by aerox (7 points) | 9 views

0 votes

0 answers

peterlinz theory of computation
mu doubt is what will be the number of states in minimum nfa and minimum dfa for this regular expression of question 1 given by L(ab*aa+bba*ab)

asked Feb 17 in Theory of Computation by aerox (7 points) | 4 views

+1 vote

0 answers

Turing Machine
As per the definition of a Turing Machine, it does not accept Epsilon. But, A → ϵ can be generated by a Unrestricted Grammar. So, how can we say that Turing Machines are the acceptors for Recursively Enumerable languages generated by Unrestricted Grammar?

asked Feb 13 in Theory of Computation by Joon88 (7 points) | 18 views

0 votes

3 answers

CFL or not ( test series qsn)
This language is CFL or not – $\Sigma = \{ a,b \} $ and $L = \{ x \# y\ |\ x,y \in \Sigma^*\ , \#\ is \ a \ constant\ and\ x \neq y \}$ please give the reason also

answered Feb 8 in Theory of Computation by kalra05 (73 points) | 211 views

+1 vote

0 answers

Self Doubt: AUTOMATA DCFL
$wxw^r|w,x\epsilon(0,1)^*$ $,|x|=5$ Is this $DCFL$ or $not?$

asked Feb 6 in Theory of Computation by Debapaul (699 points) | 37 views

0 votes

0 answers

how s and l atrributed grammar evaluted?

asked Feb 5 in Theory of Computation by spike500 (6 points) | 16 views

+1 vote

0 answers

TOC(self doubt)
How is the complement of $L=\{ww| w \epsilon(a+b)^*\}$ is $CFL$

asked Feb 5 in Theory of Computation by Pratyush Priyam Kuan (804 points) | 22 views

0 votes

1 answer

first state of clr 1 parser
I have doubts regarding first state clr1 parser of below grammer A→ Au | At | w Select the correct option which represent initial state in LR(1) state diagram. i think it should be S –> .A , $ A –> . Au , u|$ A –> . At , t|$ A → .w , u|t|$ but i am not sure.

answered Feb 4 in Theory of Computation by Srush (10 points) | 27 views

0 votes

0 answers

Made Easy:Mock
$L$:{$a^{n} b^{n+k} / n>=0,k>=1$} $\cup$ {$a^{n+k} b^{n} /n>=0,k>=3 $} Is it a DCFL?

asked Feb 3 in Theory of Computation by Sambhrant Maurya (401 points) | 49 views

0 votes

0 answers

SELF DOUBT: REGULAR LANGUAGE AND CFL
Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet $\sum$. Which of the following statement about the given language $R$, where $R=\bar{A}-B$ is $True?$ $R$ is $necessarily$ $CFL$ but $not$ $necessarily$ $regular$ R is $necessarily$ $regular$ but $infinite$ R is $necessarily$ $non$ $regular$ $None$

asked Feb 1 in Theory of Computation by Debapaul (699 points) | 32 views

0 votes

0 answers

Ambiguity in Grammar
Which CFG has equivalent unambiguous CFG ? Please help me to understand between inherently ambiguous and simple ambiguous grammar. I know how to check for ambiguity in grammar,just check if there are more than 2 derivation tree possible for a given string. But I don’t know how to check if a grammar is inherently ambiguous grammar

asked Feb 1 in Theory of Computation by s_dr_13 (16 points) | 12 views

0 votes

1 answer

for every language accepted by DPDA. there exist a NPDA. can we say that DPDA is convertable to NPDA??

answered Feb 1 in Theory of Computation by shashin (1.9k points) | 28 views

0 votes

0 answers

made easy mock 3
l is regular only if h(l) is regular. h(l) is regular only if l is regular. Which of the statement is true? I can’t understand why second statement is false if regular languages are closed under inverse homomorphism then second statement should be true

asked Feb 1 in Theory of Computation by abhinav649 (67 points) | 15 views

0 votes

0 answers

Made Easy Test Series-Mock2-TOC
Which of the following is true? I. If a Mealy Machine is converted into a Moore Machine, then the number of states don’t change. II. If a Moore Machine is converted into a Mealy Machine, then the number of states don’t change.

asked Feb 1 in Theory of Computation by Khushboo Patel (6 points) | 32 views

0 votes

0 answers

GATE FORUM: AMBIGUITY

asked Jan 31 in Theory of Computation by Debapaul (699 points) | 61 views

0 votes

0 answers

undecidability pdf given on gatecse rice's theorem

asked Jan 31 in Theory of Computation by shethnisarg (6 points) | 10 views

0 votes

0 answers

TOC : Ace test series (Semi decidable)

asked Jan 30 in Theory of Computation by Chirag Shilwant (180 points) | 22 views

0 votes

0 answers

assignment question from https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf

asked Jan 30 in Theory of Computation by abhiram144 (6 points) | 12 views

0 votes

0 answers

Applied course test series : Turing machine
Can someone explain statement I. My doubt is that if the language is accepted and rejected both by turing machine then it is decidable language which also recognized by Turing machine. So statement I should be false ,right?

asked Jan 29 in Theory of Computation by vishal burnwal (135 points) | 66 views

0 votes

0 answers

doubt in finite infinite language
is language (a+b)* defined over two terminal {a , b } is infinite or finite with infinite number of string. according to this link https://cs.stackexchange.com/questions/6609/infinite-language-vs-finite-language it is infinite but i want to get it confirmed

asked Jan 28 in Theory of Computation by mehul vaidya (22 points) | 11 views

0 votes

0 answers

ACE FLT-Automata
should not B) correct answer here?Here for 1 ‘a’ input, two aa pushing, So, it means number of ‘b’ will be double??isnot it? Someone plz chk…..

asked Jan 26 in Theory of Computation by srestha (683 points) | 18 views

0 votes

0 answers

Madeeasy test series - Number of strings present

asked Jan 26 in Theory of Computation by luc_Bloodstone (36 points) | 26 views

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

Recent questions and answers in Theory of Computation

3,513 questions

1,656 answers

10,451 comments

90,037 users