Recent questions and answers in Theory of Computation

0 votes

3 answers

1

CFL or CSL
Let L = $\{ a^n b^m | m , n \in \textbf{N} \text{ and m is multiple of n}\}$ How do we prove that this language is not CFL.

answered 2 hours ago in Theory of Computation by Raju2021 (33 points) | 102 views

+2 votes

3 answers

2

UGCNET-June-2019-II-75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$

answered 1 day ago in Theory of Computation by immanujs Active (2.9k points) | 447 views

+2 votes

3 answers

3

ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$

answered 2 days ago in Theory of Computation by immanujs Active (2.9k points) | 315 views

0 votes

1 answer

4

UGCNET-Dec2007-II: 5
Consider a Moore machine M whose digraph is : Then L(M), the language accepted by the machine M, is the set of all strings having : two or more b’s. three or more b’s. two or more a’s. three or more a’s.

answered 3 days ago in Theory of Computation by immanujs Active (2.9k points) | 19 views

0 votes

1 answer

5

NIELIT 2016 MAR Scientist B - Section C: 27
If $L$ be a language recognizable by a finite automaton, then language from $\text{{L}}$={$w$ such that $w$ is a prefix of $v$ where $v\in L$}, is a regular language. context-free language. context-sensitive language. recursive enumeration language.

answered 4 days ago in Theory of Computation by immanujs Active (2.9k points) | 18 views

0 votes

1 answer

6

NIELIT 2016 MAR Scientist B - Section C: 25
Regarding power of recognition of language, which of the following statements is false? Non deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic push-down automata are equivalent to ... to deterministic push-down automata. Multi-tape Turing machines are equivalent to single-tape Turing machines.

answered 4 days ago in Theory of Computation by immanujs Active (2.9k points) | 19 views

+1 vote

2 answers

7

theory of computtion
find regular expression of 1. S-> 01A/10B A->0B/1 B->1A/0 and 2. A->A00 /A1/0 3. S->baS/aA A->bbA/bb

answered 4 days ago in Theory of Computation by Raju2021 (33 points) | 120 views

0 votes

2 answers

8

UGCNET-Dec2006-II: 1
Which of the regular expressions corresponds to this grammar ? $S → AB/AS, A → a/aA, B → b$ $aa^*b^+$ $aa^*b$ $(ab)^*$ $a(ab)^*$

answered 5 days ago in Theory of Computation by immanujs Active (2.9k points) | 32 views

0 votes

1 answer

9

NIELIT 2016 DEC Scientist B (CS) - Section B: 24
Given two DFA's $M1$ and $M2$. They are equivalent if: $M1$ and $M2$ has the same number of states. $M1$ and $M2$ accepts the same language i.e $L(M1)=L(M2)$. $M1$ and $M2$ has the same number of final states. None of the above.

answered 5 days ago in Theory of Computation by smsubham Boss (16.8k points) | 13 views

0 votes

1 answer

10

NIELIT 2016 DEC Scientist B (CS) - Section B: 6
Which of the following is wrong? Turing machine is a simple mathematical model of general purpose computer. Turing machine is more powerful than finite automata. Turing Machine can be simulated by a general purpose computer. All of these.

answered 5 days ago in Theory of Computation by smsubham Boss (16.8k points) | 11 views

0 votes

1 answer

11

NIELIT 2016 DEC Scientist B (CS) - Section B: 3
If $L1$ is CFL and $L2$ is regular language which of the following is false? $L1-L2$ is not context free. $L1$ intersection $L2$ is context free. $\text{~} L1$ is context free. Both (A) and (C).

answered 5 days ago in Theory of Computation by smsubham Boss (16.8k points) | 14 views

0 votes

1 answer

12

UGCNET-Dec2007-II: 3
A context free grammar is : type $0$. type $1$. type $2$. type $3$.

answered 5 days ago in Theory of Computation by smsubham Boss (16.8k points) | 20 views

0 votes

1 answer

13

NIELIT 2016 MAR Scientist B - Section C: 29
The CFG $S →aS\mid bS\mid a\mid b$ is equivalent to $(a+b)$ $(a+b)(a+b)^*$ $(a+b)(a+b)$ all of these

answered Mar 31 in Theory of Computation by haralk10 Active (1.4k points) | 9 views

0 votes

1 answer

14

NIELIT 2016 MAR Scientist B - Section C: 26
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language? $L_1L_2$ $L_1\cap L_2$ $L_1\cap R$ $L_1\cup L_2$

answered Mar 31 in Theory of Computation by vg653 Junior (617 points) | 14 views

0 votes

1 answer

15

NIELIT 2016 MAR Scientist B - Section C: 24
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet ${a,b}$? $a^*b^*$ $(a\mid b)^*$ $(ab)^+$ $(a\mid b^*)$

answered Mar 31 in Theory of Computation by haralk10 Active (1.4k points) | 20 views

0 votes

0 answers

16

NIELIT 2016 MAR Scientist B - Section C: 28
Which of the following statements is correct? $A={a^nb^n\mid n= 0,1,2,3\dots}$ is regular language. Set $B$ of all strings of equal number of $a$'s and $b$'s defines a regular language. $L(A^*B^*) \cap B$ gives the set $A$. None of these.

asked Mar 31 in Theory of Computation by Lakshman Patel RJIT Veteran (61.4k points) | 9 views

0 votes

1 answer

17

NIELIT 2016 DEC Scientist B (CS) - Section B: 1
Palindromes can't be recognized by any Finite State Automata because: FSA cannot remember arbitrarily large amount of information. FSA cannot deterministically fix the midpoint. Even if the mid-Point is known an FSA cannot find whether the second half of the matches the first half. All of the above.

answered Mar 31 in Theory of Computation by Bhargav D Dave 6 (309 points) | 19 views

0 votes

0 answers

18

NIELIT 2017 July Scientist B (CS) - Section B: 48
What is the complement of the language accepted by the NFA shown below? $\phi$ $\{\epsilon\}$ $a^*$ $\{a,\epsilon\}$ $1$ $2$ $3$ $4$

asked Mar 30 in Theory of Computation by Lakshman Patel RJIT Veteran (61.4k points) | 4 views

0 votes

1 answer

19

Peter Linz Edition 4 Exercise 2.3 Question 7 (Page No. 62)
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we make a similar claim for dfa’s?

answered Mar 28 in Theory of Computation by Wilbred Anto (11 points) | 47 views

+1 vote

1 answer

20

Recognize the language
If L be a language recognizable by a finite automata, then language from {L}={w such that w is prefix of v where v belongs to L},is a a. Regular Language b. Context Free language c. Context Sensitive Language d. Recursive Enumerable Language

answered Mar 28 in Theory of Computation by habedo007 Active (3k points) | 329 views

+1 vote

1 answer

21

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) *?

answered Mar 27 in Theory of Computation by Raju2021 (33 points) | 324 views

0 votes

1 answer

22

UGCNET-Dec2004-II: 3
The context-free languages are closed for : Intersection Union Complementation Kleene Star (i) and (iv) (i) and (iii) (ii) and (iv) (ii) and (iii)

answered Mar 26 in Theory of Computation by Shobhit Joshi Loyal (5.5k points) | 18 views

0 votes

0 answers

23

UGCNET-Jan2017-III: 61
Given the following two statements: $L=\{w\mid n_{a}(w)=n_{b}(w)\}$ is deterministic context free language, but not linear. $L=\{a^{n}b^{n}\} \cup \{a^{n}b^{2n} \}$ is linear, but not deterministic context free language. Which of the following options is correct? Both (A) and (B) are false. Both (A) and (B) are true. (A) is true, (B) is false. (A) is false, (B) is true.

asked Mar 24 in Theory of Computation by jothee Veteran (108k points) | 16 views

0 votes

5 answers

24

NIELIT Scientist-B Dec 2017_53
What is the meaning of regular expression $\sum$* 001 $\sum$* ? (A) Any string containing '1' as substring (B) Any string containing '01' as substring (C) Any string containing '011' as substring (D) All string containing '001' as substring

answered Mar 22 in Theory of Computation by Vipin Tiwari (395 points) | 277 views

0 votes

4 answers

25

NIELIT Scientist-B Dec 2017_54
According to the given language, which among the following expressions does it corresponds to ? Language L={$x \epsilon${0,1}|$x$ is of length 4 or less} (A) (0+1+0+1+0+1+0+1)4 (B) (0+1)4 (C) (01)4 (D) (0+1+$\epsilon$)4

answered Mar 22 in Theory of Computation by Vipin Tiwari (395 points) | 256 views

+1 vote

3 answers

26

ISRO2020-37
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure

answered Mar 20 in Theory of Computation by smsubham Boss (16.8k points) | 169 views

0 votes

4 answers

27

NIELIT Scientist-B Dec 2017_59
Which of the following statement is true ? (A) Deterministic context free language are closed under complement (B) Deterministic context free language are not closed under complement (C) Deterministic context free language are closed under intersection with with regular set (D) All of the options

answered Mar 19 in Theory of Computation by Vipin Tiwari (395 points) | 326 views

0 votes

4 answers

28

NIELIT Scientist-B Dec 2017_60
Which of the following is true ? (A) Mealy and Moore machine are language acceptors (B) Finite State automata is language translator (C) NPDA is more powerful than DPDA (D) Mealy machine is more powerful than Mealy machine

answered Mar 19 in Theory of Computation by Vipin Tiwari (395 points) | 966 views

0 votes

1 answer

29

Toc me test me me
Minimum ba how can accept?

answered Mar 19 in Theory of Computation by smsubham Boss (16.8k points) | 66 views

+2 votes

3 answers

30

GATE2020-CS-10
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only

answered Mar 19 in Theory of Computation by smsubham Boss (16.8k points) | 1.2k views

+1 vote

4 answers

31

GATE2020-CS-8
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ

answered Mar 19 in Theory of Computation by smsubham Boss (16.8k points) | 972 views

+1 vote

1 answer

32

NIELIT Scientist-B Dec 2017_30
Let G be a grammar in CFG and let W1,W2 $\epsilon$ L(G) such that |W1|=|W2| then which of the following statement is true ? (A) Any derivation of W1 has exactly the same number of steps as any derivation of W2 (B) Different derivation have different length (C) Some derivation of W1 may be shorter the derivation of W2 (D) None of the options

answered Mar 19 in Theory of Computation by topper98 Junior (599 points) | 204 views

+1 vote

3 answers

33

NIELIT Scientist-B Dec 2017_40
A regular expression is (a+b*c) is equivalent to : (A) set of strings with either a or one or more occurrence of b followed by c. (B) (b*c+a) (C) set of strings with either a or zero or more occurrence of b followed by c. (D) Both (B) and (C)

answered Mar 19 in Theory of Computation by topper98 Junior (599 points) | 249 views

0 votes

3 answers

34

NIELIT Scientist-B Dec 2017_7
The collection of Turing recognizable language is closed under: (i) Union (ii) Intersection (iii) Complement (iv) Concatenation (v) Star closure (A) (i) Only (B) Both (i), (iv) (C) (i),(ii),(iv) and (v) (D) All of the options

answered Mar 19 in Theory of Computation by topper98 Junior (599 points) | 185 views

+1 vote

3 answers

35

NIELIT July 2017_120
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE ? A) L1' is recursive and L2' is recursively enumerable B) L1' is recursive and L2' is not recursively enumerable C) L1' and L2' are recursively enumerable D) L1' is recursively enumerable and L2' is recursive

answered Mar 19 in Theory of Computation by anurag sharma (315 points) | 91 views

0 votes

2 answers

36

NIELIT July 2017_119
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility ? A) Neither L nor L' is RE B) One of L and L' is RE but not recursive, the other is not RE C) Both L and L' are RE but not recursive D) Both L and L' are recursive

answered Mar 19 in Theory of Computation by topper98 Junior (599 points) | 80 views

0 votes

1 answer

37

Ullman (TOC) Edition 3 Exercise 3.1 Question 2 (Page No. 91)
Write regular expressions for the following languages$:$ The set of all strings of $0's$ and $1's$ such that every pair of adjacent $0's$ appears before any pair of adjacent $1's.$ The set of strings of $0's$ and $1's$ whose number of $0's$ is divisible by five.

answered Mar 15 in Theory of Computation by manikantsharma Junior (521 points) | 37 views

+5 votes

5 answers

38

GATE2020-CS-26
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only

answered Mar 14 in Theory of Computation by smsubham Boss (16.8k points) | 1k views

+3 votes

2 answers

39

what is the left quotient of a CFL with a regular language ?
If I take L=a^n b^n and R=(a+b)* so I am getting the value of L/R to be regular ,Am I correct ?

answered Mar 14 in Theory of Computation by manikantsharma Junior (521 points) | 560 views

+6 votes

4 answers

40

DCFL not closed under
DCFLs are not closed under ________ a. Complement operation b. Inverse homomorphism operation c. Reversal operation d. Prefix operation

answered Mar 13 in Theory of Computation by manikantsharma Junior (521 points) | 2.5k views

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

Recent questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments