Recent questions and answers in Theory of Computation

0 votes

1 answer

1

Deletion of Useless Symbols from a Grammar Self Doubt
S → AB/a A → BC/b B → aB/C C → aC/B How do we remove useless symbols and productions from this grammar? While solving, i found that the useful symbols are {a,b,S,A} Hence, we must delete B,C But don’t know how to proceed

Rajat Agrawal007 answered in Theory of Computation 1 day ago

by Rajat Agrawal007

136 views

1 vote

0 answers

2

Gate cse pyq
L={xy | x,y€(a+b)* , |x| =|y| , x != y} How L is cfl? How can I make PDA for this?

Bikram Das asked in Theory of Computation 5 days ago

31 views

0 votes

0 answers

3

Made Easy Test series
Consider the following language : P1 : {<M, x, k>| M is a TM and M does not halt on x within k steps} P2 : {<M>| M is TM and L(M) = $\phi$} P3 : {<M>| M is a TM and L(M) = finite language} The number of problems which are not RE is/are _______ ?

Aashay kaurav asked in Theory of Computation 6 days ago

by Aashay kaurav

42 views

0 votes

0 answers

4

Self doubt
Given an NFA N, whether there is a PDA P such that N and P accept the same language. It is decidable or not

samarpita asked in Theory of Computation 6 days ago

14 views

0 votes

0 answers

5

Theory of computation
Construct predictive parser for the following grammar and also check for the validity of the input string of your choice. bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor → not bfactor | (bexpr) | true | false

Adaboina sushmitha asked in Theory of Computation Oct 11

by Adaboina sushmitha

27 views

1 vote

1 answer

6

can someone share the approach for the following que
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not. Can someone share the approach for second part.

Shaik Masthan answered in Theory of Computation Oct 11

by Shaik Masthan

33 views

0 votes

0 answers

7

Construct compiler
Given the grammarS->XS | dS | ε ,X->Y | Zb | aY,Y->eZ,Z->e Construct the predictive parsing tableand show the moves made by the predictive parser on the input “dace

Adaboina sushmitha asked in Theory of Computation Oct 10

by Adaboina sushmitha

26 views

0 votes

1 answer

8

Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.

raja11sep answered in Theory of Computation Oct 9

58 views

2 votes

1 answer

9

Number of final states
A FA accepting language L(A) has n states and m transition. ∑ = {a, b} L(A) is given as L(A)={ x | if x ∊ L(A) then u ∊ L(A) for $∃u, v ∊ ∑^{*}$ where x=uv } Find number of final state in above DFA?

Yaman Sahu answered in Theory of Computation Oct 9

48 views

0 votes

2 answers

10

Regular expressons
The minimum number of states in an equivalent finite automata for the given regular expression are _____ (a(a(a(a(a(ab)*b)*b)*b)*b)*b)*

Vishal_kumar98 answered in Theory of Computation Oct 8

by Vishal_kumar98

84 views

0 votes

1 answer

11

Applied Test Series
The language accepted by the given PDA is

Yaman Sahu answered in Theory of Computation Oct 7

38 views

0 votes

1 answer

12

Cross product of dfa in toc
if a automata in dfa contains N states and further automatic contains M states then in the final DFA obtained from cross product method will contain N*M States. First ,is the above statement always true and if it is then will there be a need to minimize it after cross product to get minimal dfa in questions which asks for more than one condition to exist in dfa.

Aashay kaurav answered in Theory of Computation Oct 6

by Aashay kaurav

37 views

0 votes

1 answer

13

ace test series
number of 3 state dfa with designated initial stat can be constructed over the alphabet {0,1,2} with exactly 2 final states is a)3^8 b)3^9 c)3^10 d)3^11

raja11sep answered in Theory of Computation Oct 6

32 views

0 votes

1 answer

14

ace test series
identify options for which operation CFL's are not closed? a)union, complement b)complement, intersection

Yaman Sahu answered in Theory of Computation Oct 6

43 views

1 vote

1 answer

15

Applied Test Series
How to approach with such questions. Do we have to generate strings to validate the property of the grammars ?

Yaman Sahu answered in Theory of Computation Oct 4

55 views

31 votes

8 answers

16

GATE IT 2007 | Question: 73
Consider the regular expression $R = (a + b)^* \ (aa + bb) \ (a + b)^*$ Which one of the regular expressions given below defines the same language as defined by the regular expression $R$ ? $(a(ba)^* + b(ab)^*)(a + b)^+$ $(a(ba)^* + b(ab)^*)^*(a + b)^*$ $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$ $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$

ShouvikSVK answered in Theory of Computation Oct 4

9.4k views

0 votes

2 answers

17

Made Easy Test Series
Why option B is wrong

sukesh_reddy answered in Theory of Computation Oct 1

by sukesh_reddy

154 views

2 votes

1 answer

18

Why can't linear bounded automata accept an empty string?
The linear bounded automata (LBA) is defined as follows: A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with the restriction that ... explains why LBA cannot accept empty string (which is why CSG does not have lambda production). Can anyone explain?

manikantsharma answered in Theory of Computation Sep 27

by manikantsharma

792 views

0 votes

1 answer

19

Linear Bounded Automata
In LBA why not tape length same as input length? Why tape length linear multiple of input length? Why not it non linear?

manikantsharma answered in Theory of Computation Sep 27

by manikantsharma

1.1k views

0 votes

1 answer

20

#RegularExpression
Whats the Logic behind Kleene Closure of null set is string with 0 length??

Vishal_kumar98 answered in Theory of Computation Sep 26

by Vishal_kumar98

46 views

2 votes

2 answers

21

Applied roots test series question.
Which of the following is/are undecidable? A = { M| M is TM that accepts exactly all the odd length strings} L = { M|M is a TM and L(M) is infinite} EQ = {<D,E> | D is a DFA , E is a regular expression and L(D) = L(E ... According the key option a' is also UNDECIDABLE why is that, where am I going wrong and is the idea I've thought for option b' correct?

rish1602 answered in Theory of Computation Sep 21

85 views

0 votes

1 answer

22

LR(k) and CFL
I am quite confused in this . I have seen in many answers related to LR(k), that DCFL have one to one correspondence with LR(k) grammars. Means if a language is DCFL then it would definitely have a LR(k) grammar and if there is an LR(k) ... any ncfl. So, how for some unambiguous ncfl there exists an LR(k) grammar??? Please someone can provide a correct argument regarding this.

minalBallav answered in Theory of Computation Sep 20

55 views

0 votes

1 answer

23

CFL or DCFL?
Is the language L = {a^nb^m : n = m or n = m + 2} deterministic? Please anybody can clarify it.

atulcse answered in Theory of Computation Sep 18

76 views

0 votes

1 answer

24

Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?

Ankita87077 answered in Theory of Computation Sep 17

177 views

5 votes

2 answers

25

GATE CSE 2021 Set 2 | Question: 47
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$

Mohitdas answered in Theory of Computation Sep 17

2k views

0 votes

2 answers

26

KTU University Exam 2021
Let r1=(0+1)*, r2=0*1+10*+0*+1*. What is the length of the smallest string that is present in language corresponds to regular expression r1 and not present in language corresponds to regular expression r2. 2 3 1 none of the above

Mohitdas answered in Theory of Computation Sep 17

125 views

1 vote

2 answers

27

Chomskey Normal Form
State true/false In CNF , S-> espilon and Start symbol can appear on RHS side of production.

Ankita87077 answered in Theory of Computation Sep 16

1.4k views

1 vote

2 answers

28

Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.

rish1602 answered in Theory of Computation Sep 16

202 views

0 votes

1 answer

29

#theory-of-computation
If L1 = {a^nb^nc^md^m | n,m>=0} L2 = {a^nb^n | n>=0} L3 = {c^md^m | m>=0} Then L1 – L2.L3(concatenation) is? Regular CSL CFL REL(recursive enumerable)

Yaman Sahu answered in Theory of Computation Sep 14

87 views

0 votes

1 answer

30

Peter Linz Edition 4 Exercise 5.2 Question 5 (Page No. 145)
Let $G = (V, T, S, P)$ be an s-grammar. Give an expression for the maximum size of $P$ in terms of $|V|$ and $|T|$.

Ankita87077 answered in Theory of Computation Sep 13

83 views

9 votes

1 answer

31

Acceptance of languages by DPDA with empty stack Vs NPDA with empty stack
There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). ... by final state are not equivalent in case of DPDA but it is equivalent in case of NPDA

hetgate22 answered in Theory of Computation Sep 11

2.6k views

0 votes

1 answer

32

Peter Linz Edition 4 Exercise 4.2 Question 14 (Page No. 114)
Find an algorithm for determining whether a regular language $L$ contains an infinite number of even-length strings.

Ankita87077 answered in Theory of Computation Sep 11

88 views

3 votes

2 answers

33

TOC-Turing Machine
Consider the given below Turing Machine and identify the correct language accepted: (a+b)*aa(a+b)* b*a(bb*a)*a b*ab*a None of these The answer is given as (1). But I think (3) is correct as well. Can anyone tell me why only (1) is correct.

rish1602 answered in Theory of Computation Sep 10

462 views

4 votes

2 answers

34

Ace Test Series: Theory Of Computation - Turing Machine
When a Multi-tape TM of time complexity T(N) is reduced to a single tape turing machine, the complexity can go upto?

rish1602 answered in Theory of Computation Sep 10

386 views

3 votes

2 answers

35

Made Easy Test Series:TOC-Turing Machine
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________

rish1602 answered in Theory of Computation Sep 10

530 views

23 votes

3 answers

36

GATE CSE 2001 | Question: 1.5
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free

imkeshav answered in Theory of Computation Sep 7

10.8k views

1 vote

0 answers

37

#TOC NPTEL ASSIGNMENT Question about reducibility
Please help me understand this question. I have searched on internet, but not avail. Click this to see the question

iarnav asked in Theory of Computation Sep 6

by iarnav

59 views

57 votes

10 answers

38

GATE CSE 2010 | Question: 39
Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$

Ankita87077 answered in Theory of Computation Sep 5

14.7k views

14 votes

4 answers

39

GATE CSE 1987 | Question: 2h
State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.

ProtonicRED answered in Theory of Computation Aug 23

2k views

2 votes

3 answers

40

UGCNET-June2016-III: 56
Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct? $\overline L$ is context free and $L^k$ is not context free for any $k\ge1$ $\overline L$ is not context free and $L^k$ is context free for any $k\ge1$ Both $\overline L$ and $L^k$ for any $k\ge1$ are context free Both $\overline L$ and $L^k$ for any $k\ge1$ are not context free

TheShivam answered in Theory of Computation Aug 22

289 views

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

Follow @gateoverflow

GATE Overflow

Recent questions and answers in Theory of Computation

Search GATE Overflow