Recent questions and answers in Theory of Computation - GATE Overflow

First time here? Checkout the FAQ!

x

+14 votes

7 answers

1

ISRO2016-38
What is the highest type number that can be assigned to the following grammar? $$S\to Aa,A\to Ba,B \to abc$$ Type 0 Type 1 Type 2 Type 3

answered 3 hours ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 3.8k views

+1 vote

1 answer

2

Peter linz
Question 8.

answered 8 hours ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 8 views

+1 vote

1 answer

3

Peter linz
Question 4.

answered 8 hours ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 6 views

0 votes

2 answers

4

Peter Linz
Question 11.

answered 9 hours ago in Theory of Computation by Sambit Kumar Active (2k points) | 12 views

+1 vote

1 answer

5

toc#cfl
can someone give an example CFL is not closed under complement.???

answered 10 hours ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 9 views

0 votes

2 answers

6

TOC#DECIDABLE
L1= RE U NOT RE. $L2=RE\cap NOT RE$. WHERE RE IS recursively enumerable. then L1 and L2 are ???

answered 1 day ago in Theory of Computation by Soumya29 Loyal (5.2k points) | 25 views

0 votes

1 answer

7

toc#decidable
If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be decidable??? can i say L1 and L2 is re and re is closed under union operation so it is decidable??

answered 1 day ago in Theory of Computation by eyeamgj Active (1.6k points) | 22 views

+2 votes

1 answer

8

regular language
C = {ak | k is multiple of n }. Then how to show that for each n>=1, the language C is regular.

answered 1 day ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 44 views

0 votes

0 answers

9

toc#decidible
can some one give an example a language is recursive but not CSL??

asked 1 day ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 40 views

+1 vote

1 answer

10

Engnineers Academy Workbook
Which one of the following doesn’t generate same language as rest? (i) (a+b)*a(a+b)*a(a+b)* (ii) b * a b * a (a + b)* (iii) (a + b)* a b* a b* (iv) b * a (a + b)* a b*

answered 1 day ago in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 25 views

0 votes

0 answers

11

Help me understand this statement from Theory of Computation by Peter Linz

asked 3 days ago in Theory of Computation by ankit aingh (13 points) | 43 views

+1 vote

1 answer

12

Pumping lemma
Reduce the following grammar in G.N.F S ->AA/b S ->SS/a How to solve this type of question ?

answered 3 days ago in Theory of Computation by Kushagra Chatterjee Junior (827 points) | 28 views

0 votes

1 answer

13

Np Hard Problems
Are NP-Hard problems Semi decidable or Decidable or not even semidecidable? I know NP class is decidable as there is polynomial time NTM.But in the following figure in case there are some NP hard problems that are lying outside of NP.Problems which are NP-hard but not NPC.Can these also be solved in polynomial time by NTM?

answered 3 days ago in Theory of Computation by Arjun Veteran (339k points) | 69 views

0 votes

0 answers

14

Context free grammars
Why is CFG not considered adequate for describing natural languages ?

asked 4 days ago in Theory of Computation by PriyankaS (9 points) | 43 views

0 votes

2 answers

15

context free languages
State True/False: "Any finite subset of {a,b}* is a context free language."

answered 5 days ago in Theory of Computation by viplovekadre19 (35 points) | 176 views

0 votes

3 answers

16

An Intro. to formal lang. and automata(Peter Linz) chapter 2.....2.1 ques 6

answered 5 days ago in Theory of Computation by Sambit Kumar Active (2k points) | 243 views

0 votes

1 answer

17

Closure Properties Of Languages
Subset problem in undecidable for DCFL's , now consider the following argument given below. G1 and G2 are DCFL,the algorithm to test whether L(G1) is a subset of L(G2) or not. Check for equivalence (L(G1)=L(G2)) ,if yes then we're ... the above procedure did solve the subset problem. So my question is that,if the above procedure is not correct how can i prove it ?

answered 5 days ago in Theory of Computation by sonveer tomar 1 Junior (891 points) | 16 views

0 votes

1 answer

18

Regular expression
Write the regular expression for the language containing the string over{0,1} in which there are atleast two occurence of 1's between any two occurence of 0's.

answered 6 days ago in Theory of Computation by Mk Utkarsh Boss (11.9k points) | 16 views

0 votes

1 answer

19

Construct a DFA
Construct a DFA that accepts a language generated by a grammar S->abA A->baB B->aA|bb Find tha DFA and regular expression

answered Apr 14 in Theory of Computation by Hitesh (369 points) | 33 views

0 votes

1 answer

20

Regular grammar in TOC
Find the regular grammar for $L=\{a^nb^m \mid n+m \text{ is even}\}$

answered Apr 14 in Theory of Computation by pankaj_vir Loyal (6.3k points) | 25 views

0 votes

0 answers

21

Context Free Grammar
Find the rank of A in the given context free grammar A->BC B->a C->b I think the rank of A in this grammar will be 2. Let me know if I am right and if not then please help with the right answer.

asked Apr 14 in Theory of Computation by hrcule (113 points) | 33 views

0 votes

1 answer

22

Regular expression

answered Apr 14 in Theory of Computation by Kushagra Chatterjee Junior (827 points) | 46 views

+23 votes

4 answers

23

GATE2015-2_35
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ $X_2 = ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$

answered Apr 14 in Theory of Computation by Ayan Mondol (27 points) | 2.6k views

0 votes

1 answer

24

Context Free Languages
Answer with explanation will be acknowledged.

answered Apr 13 in Theory of Computation by Deepakk Poonia (Dee) Active (2.9k points) | 41 views

+2 votes

2 answers

25

Brute Force Parsing
Which of the following can be said about the Exhaustive search parsing or brute force parsing ? It is inefficient as the time taken is proportional to the length of the string. The parser always terminates on the strings in the $L(G)$. The parser always terminates on the strings not in $L(G)$. $\text{1 & 2}$ $\text{2 & 3}$ $\text{1 & 3}$ $\text{1, 2 & 3}$

answered Apr 13 in Theory of Computation by meghna (145 points) | 100 views

+19 votes

4 answers

26

GATE2006-IT-81
Let $L$ be a regular language. Consider the constructions on $L$ below: $\text{repeat} (L) = \{ww \mid w \in L\}$ $\text{prefix} (L) = \{u \mid \exists v : uv \in L\}$ $\text{suffix} (L) = \{v \mid \exists u: uv \in L\}$ $\text{half} (L) = \{u \mid \exists v: ... is best suited to support your answer above? $(a + b)^*$ $\{\epsilon, a, ab, bab\}$ $(ab)^*$ $\{a^nb^n \mid n \geq 0\}$

answered Apr 13 in Theory of Computation by Karthik Kumar Mudr 1 (115 points) | 1.9k views

+12 votes

2 answers

27

GATE2006-IT-80
Let $L$ be a regular language. Consider the constructions on $L$ below: repeat $(L) = \{ww \mid w \in L\}$ prefix $(L) = \{u \mid ∃v : uv \in L\}$ suffix $(L) = \{v \mid ∃u : uv \in L\}$ half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$ Which of the constructions could lead to a non-regular language? Both I and IV Only I Only IV Both II and III

answered Apr 13 in Theory of Computation by Karthik Kumar Mudr 1 (115 points) | 1.2k views

0 votes

1 answer

28

Introduction to Computer Theory
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?

answered Apr 13 in Theory of Computation by Kumar Ashish (397 points) | 21 views

0 votes

1 answer

29

#toc #regular languages #homomorphism
Which of the following are true for all regular languages and all homomorphisms, Justify with examples.

answered Apr 12 in Theory of Computation by Puja Das (11 points) | 25 views

0 votes

1 answer

30

Introduction to Computer Theory
Give CFG for the following language L =$ {(a^{m})(b^{m+n})(c^{n}) | m,n= 0,1,2,.....}$

answered Apr 12 in Theory of Computation by Tesla! Boss (15.4k points) | 39 views

+5 votes

2 answers

31

ISI2015-CS-5a
Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular. Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 \cup L_2$ is regular.

answered Apr 12 in Theory of Computation by Karthik Kumar Mudr 1 (115 points) | 233 views

0 votes

1 answer

32

Exam - Foundation of Computing - 2018
Find a context-free grammar for the following language: L = { a^m b^m c^k | k <= m } (in order to show that the language is context-free)

answered Apr 12 in Theory of Computation by Deepakk Poonia (Dee) Active (2.9k points) | 32 views

0 votes

1 answer

33

#toc #regular grammars
Is it possible to write a Left Linear grammar for a given language directly, or we first write its Right linear grammar and then convert it subsequently? Please explain with some example.

answered Apr 12 in Theory of Computation by Deepakk Poonia (Dee) Active (2.9k points) | 27 views

+1 vote

3 answers

34

#Theory of computation #Regular Expresions

answered Apr 11 in Theory of Computation by meghna (145 points) | 77 views

0 votes

0 answers

35

Codes of Turing Machine
As codes of turing machines are unique for a given turing machine,Say no i have two turing machines ,one for even a's and other for odd a's over the input a,b. Now both these machines will have same transition function but ... state and codes of turing machine is the representation of transition function,so how do these two turing machines will have different codes?

asked Apr 11 in Theory of Computation by rahul sharma 5 Boss (23k points) | 42 views

+2 votes

1 answer

36

Prove that language is CFL
$ L= \{ w1 w2 | w1,w2 ∈Σ^{+} ,w1!=w2 \} $ How can i prove that it is CFL?

answered Apr 11 in Theory of Computation by Deepakk Poonia (Dee) Active (2.9k points) | 57 views

0 votes

0 answers

37

what is cnf for following grammer ?
Eliminate ε productions, unit productions, useless symbols and then rewrite the resulting grammar in the Chomsky Normal Form (in that order) for the following two input grammars: S -> 0E0 | 1FF | ε E -> G F -> S | E G -> S | ε

asked Apr 10 in Theory of Computation by hem chandra joshi Active (4.3k points) | 20 views

+1 vote

1 answer

38

Number of States in FA
Can number of states in minimized DFA be less than number of states than minimal NFA from which it is converted?

answered Apr 9 in Theory of Computation by abhishekmehta4u Loyal (9.7k points) | 77 views

0 votes

0 answers

39

Worst Case in NFA to DFA Conversion
Can you give an example of NFA which has n states and its corresponding DFA has 2^n states?

asked Apr 8 in Theory of Computation by smsubham Loyal (6k points) | 39 views

+1 vote

0 answers

40

whether the given languages are context free or not

asked Apr 8 in Theory of Computation by Sambit Kumar Active (2k points) | 77 views

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

Follow @csegate

Gatecse

Recent questions and answers in Theory of Computation

34,816 questions

41,802 answers

119,041 comments

41,445 users