Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 2 &2&3&3&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count} & 3 &3&4&3&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks} & 8 &8&11&9&8&8&12&9&9&9&\bf{8}&\bf{9.1}&\bf{12}\\\hline
\end{array}}}$$

Recent questions in Theory of Computation

0 votes

0 answers

6151

NDPA
Consider the NPDA < Q = {q0, q1, q2}, ∑ = {0, 1}, τ = {0, 1, &perp; }, δ, q0, &perp; , F = {q2} >, where (as per usual convention) Q is the set of states, ? is the input ... of accepting states, The state transition is as follows Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?

Consider the NPDA < Q = {q0, q1, q2}, ∑ = {0, 1}, τ = {0, 1, &perp; }, δ, q0, &perp; , F = {q2} >, where (as per usual convention) Q is the set of states, ?...

shalini j

318 views

shalini j asked Jan 8, 2016

3 votes

2 answers

6152

TOC - What is quotient operation ?
Let A = {(a*b*)} and B = {bb, ba, bbb}. Then A/B represents of the following language when / is quotient operation. a) ∅ b) {b*} c) {a*b*} d) None What is the quotient operation here, and how to operate it on given languages.

Let A = {(a*b*)} and B = {bb, ba, bbb}. Then A/B represents of the following language when / is quotient operation.a) ∅b) {b*}c) {a*b*}d) NoneWhat is the quotient o...

prathams

3.7k views

prathams asked Jan 8, 2016

1 votes

2 answers

6153

Equivalence of Turing Machines.
Consider the following two arguments: "For every non deterministic TM M1 there exists an equivalent deterministic TM M2 recognizing the same language." "Equivalence of two Turing Machines is undecidable" These two arguments seem a bit contradicting. What can be concluded from these two arguments?

Consider the following two arguments:"For every non deterministic TM M1 there exists an equivalent deterministic TM M2 recognizing the same language.""Equivalence of two ...

अनुराग पाण्डेय

3.5k views

अनुराग पाण्डेय asked Jan 6, 2016

2 votes

1 answer

6154

Question on reducibility
Please check if the given answer is correct or not.

Please check if the given answer is correct or not.

shikharV

835 views

shikharV asked Jan 4, 2016

10 votes

1 answer

6155

can we find out minimum numbers of states in DFA if NFA has n states

wxyz

11.8k views

wxyz asked Jan 4, 2016

1 votes

1 answer

6156

Regular - CFG
Consider the language L1 = { apbqcr / p,q,r >= 0} and L2 = { apbqcr / p,q,r >= 0 and p=r} Then L1 - L2 is regular of CFL ?

Consider the language L1 = { apbqcr / p,q,r >= 0} and L2 = { apbqcr / p,q,r >= 0 and p=r} Then L1 - L2 is regular of CFL ?

Mojo-Jojo

639 views

Mojo-Jojo asked Jan 4, 2016

1 votes

1 answer

6157

Language and its compliment
Given $(L')^* = (L^*)' where ' is complement operation. $L$ is ? $ \phi, \{\epsilon \}$ and $ \Sigma^*$ $\{\epsilon \}$ and $\Sigma^*$ $ \phi $ and $\{\epsilon \} $ $L$ is not any of $\phi, \{\ ... $\Sigma^*$ Please someone explain the meaning of ∅ and comp(∅) also. This question got me confused over the meaning of ∈ also.

Given $(L')^* = (L^*)' where ' is complement operation.$L$ is ?$ \phi, \{\epsilon \}$ and $ \Sigma^*$$\{\epsilon \}$ and $\Sigma^*$$ \phi $ and $\{\epsilon \} $$L$ is no...

Utk

568 views

Utk asked Jan 4, 2016

1 votes

1 answer

6158

REGULAR EXPRESSION - Inverse homomorphism
Let r = (10 + 0) * 11(0 + 1) * be a regular expression for the regular language L and let h(0) = ab and h(1) = ba a homomorphism. What is a regular expression for h(L)? How about h −1 (L′) if L′ is given by the regular expression r ′ = (ab + a) * bb(a + b) *?

Let r = (10 + 0) * 11(0 + 1) * be a regular expression for the regular language L and let h(0) = ab and h(1) = ba a homomorphism. What is a regular expression for h(L)? H...

bahirNaik

747 views

bahirNaik asked Jan 4, 2016

2 votes

1 answer

6159

Turing Recognizable L
If $L$ is Turing-recongnizable. Then (A) $L$ and $\bar{L}$ must be decidable. (B) $L$ must be decidable but $\bar{L}$ need not be. (C) Either $L$ is decidable or $\bar{L}$ is not Turing recognizable. (D) None of above.

If $L$ is Turing-recongnizable. Then(A) $L$ and $\bar{L}$ must be decidable.(B) $L$ must be decidable but $\bar{L}$ need not be.(C) Either $L$ is decidable or $\bar{L}$ i...

bahirNaik

836 views

bahirNaik asked Jan 4, 2016

1 votes

2 answers

6160

Is this language DCFL
Hi , my question is : is this language D ( w x wR ) DCFL or Non deterministic CFL ?

Hi , my question is : is this language D ( w x wR ) DCFL or Non deterministic CFL ?

worst_engineer

1.4k views

worst_engineer asked Jan 4, 2016

0 votes

1 answer

6161

Two languages reducible to each other in polynomial time. Which is false option for them?
If Language L1 is reducible to L2 and L2 reducible to L1, then shouldn't they both be Recursively Enumerable Languages? I am really confused with the option given. Source : testbook.com live test on 3rd January, 2016

If Language L1 is reducible to L2 and L2 reducible to L1, then shouldn't they both be Recursively Enumerable Languages? I am really confused with the option given.Source ...

Utk

701 views

Utk asked Jan 4, 2016

3 votes

1 answer

6162

MadeEasy Test Series: Theory of Computation- Closure Property
Which of the following is false ? a. Union of two recursive languages is recursive b. Intersection of regular and recursive language is recursive c. Union of regular language and recursive language is recursive d. None of these. please give examples of each option.. and also describe intersection of regular and recursive is recursive..

Which of the following is false ?a. Union of two recursive languages is recursive b. Intersection of regular and recursive language is recursivec. Union of regular langua...

resuscitate

2.3k views

resuscitate asked Jan 3, 2016

1 votes

3 answers

6163

English Terminology
Do we reduce PCP problem to our problem X to show that X is undecidable OR we reduce the problem X to PCP to show X's undecidability ?. A question has confused me in the terminology.

Do we reduce PCP problem to our problem X to show that X is undecidable OR we reduce the problem X to PCP to show X's undecidability ?. A question has confused me in the...

Mojo-Jojo

645 views

Mojo-Jojo asked Jan 3, 2016

7 votes

1 answer

6164

DPDA (Empty Stack vs Final State)
" DPDA acceptance with empty stack" & " DPDA acceptance with Final State" are not equivalent. Comment on their dissimilarities & why they are not equivalent ?

" DPDA acceptance with empty stack" & " DPDA acceptance with Final State" are not equivalent. Comment on their dissimilarities & why they are not equivalent ?

Himanshu1

3.1k views

Himanshu1 asked Jan 3, 2016

1 votes

3 answers

6165

Dead state
If we are asked the number of states in minimum DFA, then we have to count dead state , right ?

If we are asked the number of states in minimum DFA, then we have to count dead state , right ?

Mojo-Jojo

1.4k views

Mojo-Jojo asked Jan 3, 2016

1 votes

0 answers

6166

Output Of PDA.

bahirNaik

731 views

bahirNaik asked Jan 3, 2016

0 votes

1 answer

6167

Which of the following is false?
Which of the following statement is false? (A) Whether one DPDA is equal to other. (B) Whether a CFG accepts the language of all strings. (C) If a CFG has an equivalent DPDA. (D) Two CFG generates the common words. (i) Only D (ii) B,C,D (iii) A,D (iv) only A

Which of the following statement is false?(A) Whether one DPDA is equal to other. (B) Whether a CFG accepts the language of all strings.(C) If a CFG has an equivalent DPD...

bahirNaik

534 views

bahirNaik asked Jan 3, 2016

1 votes

1 answer

6168

TOC: Regular Expression How to apprach
Consider the regular expression $R=(a+b)^*(aa+bb)(a+b)^*$. Which one of the following regular expressions describes the same language as described by $R$? $R_1 = (a(ba)^*(a+bb)+b(ab)^*(b+aa))(a+b)^+$ $R_2= (a(ba)^*(a+bb)+b(ab)^*(b+aa))(a+b)^*$ $R_3= (a(ba)^*+b(ab)^*)+(a+b)^*$ $R_4= (a(ba)^*+b(ab)^*)(a+b)^+$ How to approach this ?

Consider the regular expression $R=(a+b)^*(aa+bb)(a+b)^*$. Which one of the following regular expressions describes the same language as described by $R$?$R_1 = (a(ba)^*(...

Prasanna

658 views

Prasanna asked Jan 2, 2016

1 votes

1 answer

6169

TOC : Complement of RE
Let $L$ be the language over the alphabet $\Sigma$={0,1} defined by the regular expression $(0+1)^*00(0+1)^*$. Which one of the following regular expressions defines the complement of $L$? a) $1^*01^*01^*$ b) $(10)^*11(10)^*$ c) $(0+10)^*(1+ \epsilon)$ d) $(1+01)^*(0+ \epsilon)$ Why Option 2 is wrong ?

Let $L$ be the language over the alphabet $\Sigma$={0,1} defined by the regular expression $(0+1)^*00(0+1)^*$. Which one of the following regular expressions defines the ...

Prasanna

1.5k views

Prasanna asked Jan 2, 2016

5 votes

2 answers

6170

How to construct compound Automata ? and find the no of states in minimal FA ?
Construct Minimal FA that accept all binary strings ends with 01 AND length of string is EVEN . Also find no of states in its minimal FA

Construct Minimal FA that accept all binary strings ends with 01 AND length of string is EVEN .Also find no of states in its minimal FA

2.7k views

pC asked Jan 2, 2016

Page:

« prev
1
...
303
304
305
306
307
308
309
310
311
312
313
...
347
next »

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true