Search results for gate+theory-of-computation / GATE Overflow for GATE CSE

3 votes

3 answers

21

Virtual Gate Test Series: Theory Of Computation - Languages
Consider the following context-sensitive productions $\\S\rightarrow bSb\, |\, AcA \\Ab\rightarrow A,\, Ab\rightarrow b \\bA\rightarrow b,\, bA\rightarrow A$ Let $G$ be grammar given by all the rules except the last, and let $G'$ be the ... is regular Both $L(G)$ and $L(G')$ are regular None of $L(G)$ and $L(G')$ are regular

Consider the following context-sensitive productions$\\S\rightarrow bSb\, |\, AcA \\Ab\rightarrow A,\, Ab\rightarrow b \\bA\rightarrow b,\, bA\rightarrow A$Let $G$ be gra...

shreshtha5

680 views

shreshtha5 asked Dec 5, 2015

2 votes

3 answers

22

Virtual Gate Test Series: Theory Of Computation - Regular Languages
The language given is $\text{$L = \{ w | w $ contains an equal no of occurrences of substrings '$ab'$ and $'ba' \}.$ }$ $L$ is regular $?$ Note$:-$ $aba ∈ L $since $'aba'$ contains $1$ occurrence of $'ab'$ and $1$ occurrence of $'ba'$ but $ abab ∉ L$

The language given is $\text{$L = \{ w | w $ contains an equal no of occurrences of substrings '$ab'$ and $'ba' \}.$ }$ $L$ is regular $?$Note$:-$ $aba ∈ L $since $'a...

smartmeet

4.3k views

smartmeet asked Dec 8, 2016

0 votes

1 answer

23

Virtual Gate Test Series: Theory Of Computation - Languages
Answe is B, but why is L2 not regular? How to solve it? For L2, $ y=x^{1/n}$ I am not understanding why is this not right?

Answe is B, but why is L2 not regular? How to solve it? For L2, $ y=x^{1/n}$ I am not understanding why is this not right?

Purple

446 views

Purple asked Jan 12, 2017

0 votes

0 answers

24

User GATE 2006
Let L1={0n+m1n0m∣n,m≥0}L1={0n+m1n0m∣n,m≥0}, L2={0^n+m 1^n+m 0^m∣n,m≥0}L2={0^n+m 1^n+m 0^m∣n,m≥0} and L3={0^n+m 1^n+m 0^n+m∣n,m≥0}L3={0^n+m 1^n+m 0^n+m∣n,m≥0}. Which of these languages are NOT context free? L1 only L3 only L1 and L2 L2 and L3 THE ABOVE LANGUAGE HAS EPLSILON SO ITS NOT RECOGONIZED BY ANY TURING MACHINE HENCE IS IT NOT RECURSIVELY ENUMERABLE??

LetL1={0n+m1n0m∣n,m≥0}L1={0n+m1n0m∣n,m≥0},L2={0^n+m 1^n+m 0^m∣n,m≥0}L2={0^n+m 1^n+m 0^m∣n,m≥0} andL3={0^n+m 1^n+m 0^n+m∣n,m≥0}L3={0^n+m 1^n+m 0^n+m∣...

Venkat Sai

259 views

Venkat Sai asked Oct 3, 2017

1 votes

1 answer

25

Virtual Gate Test Series: Theory Of Computation - Regular Languages
Which one of the following languages over the alphabet ${0, 1}$ is regular$?$ $(A)$ The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively $(B)$ The language of palindromes, i.e., bit strings $x$ ... The kleene closure $L^{*},$ where $L$ is the language in $(C)$ above Ans is $D$ please explain$?$

Which one of the following languages over the alphabet ${0, 1}$ is regular$?$$(A)$ The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively$...

indrajeet

915 views

indrajeet asked Feb 5, 2017

0 votes

1 answer

26

Virtual Gate Test Series: Theory Of Computation - Languages
For $A,B\subseteq \Sigma ^{*},$ define $A/B=\{x\in\Sigma^{*}\mid \exists y\in B,xy\in A\}$ If $L$ is a $\text{CFL}$ and $R$ is $\text{Regular},$ then $L/R$ is$?$ Regular CFL but not Regular Recursive but not CFL None of the above

For $A,B\subseteq \Sigma ^{*},$ define$A/B=\{x\in\Sigma^{*}\mid \exists y\in B,xy\in A\}$If $L$ is a $\text{CFL}$ and $R$ is $\text{Regular},$ then $L/R$ is$?$RegularCFL ...

smartmeet

788 views

smartmeet asked Jan 12, 2017

0 votes

1 answer

27

Virtual Gate Test Series: Theory Of Computation - CFL Self Concatenation
Let $L$ be a given context-free language over the alphabet $\{a, b\}$ then $L_{2} = L·L$ is $\text{CFL.}$ Is $\text{CFL.}$ in general closed under $\text{self-concatenation?}$ If $L={ a^nb^n }$ then $L.L= { a^nb^na^nb^n }$ $\text{(or)}$ $L.L= { a^nb^na^mb^m } ?$

Let $L$ be a given context-free language over the alphabet $\{a, b\}$ then $L_{2} = L·L$ is $\text{CFL.}$Is $\text{CFL.}$ in general closed under $\text{self-concatenat...

yg92

501 views

yg92 asked Jan 25, 2017

2 votes

2 answers

28

Virtual Gate Test Series: Theory Of Computation - DFA
Number of states in the $\text{DFA}$ accepting the language $L=\{a^{n}b^{n}|1\leq n\leq 3\}$ over $\sum=\{a,b\}.$

Number of states in the $\text{DFA}$ accepting the language $L=\{a^{n}b^{n}|1\leq n\leq 3\}$ over $\sum=\{a,b\}.$

Jason GATE

583 views

Jason GATE asked Jan 8, 2017

0 votes

0 answers

29

Virtual Gate Test Series: Theory Of Computation - Context Sensitive Grammar
How can L(G) be regular? If we derive bSb --> bAcAb, now we have Ab-->b but we do not have the production bA since G is all production except last. So there is no production for A or bA. How can we go further?

How can L(G) be regular?If we derive bSb bAcAb, now we have Ab >b but we do not have the production bA since G is all production except last. So there is no production ...

Purple

429 views

Purple asked Jan 12, 2017

1 votes

1 answer

30

Calicut Gate Academy Test Series
The Java language is: A context free language A context sensitive language A regular language Parsable fully only by a Turing machine

The Java language is:A context free languageA context sensitive languageA regular languageParsable fully only by a Turing machine

PEKKA

316 views

PEKKA asked Dec 5, 2016

3 votes

0 answers

31

GATE CSE 1990 | Question: 15b
Complete the following production rules which generate the language:$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$ where variables $R$ and $Q$ ... $Q \rightarrow R'c$ $cR' \rightarrow ...$ $bR' \rightarrow ...$ $aR' \rightarrow a...$

Complete the following production rules which generate the language:$$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$$ where variables $R$ and $Q$ are used t...

makhdoom ghaya

712 views

makhdoom ghaya asked Nov 26, 2016

1 votes

1 answer

32

Calicut Gate Academy Test Series | TOC Q32
Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ={0,1} Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}. Then L is Recursively enumerable Not Recursively enumerable Recursive Udecidable (Multiple Options May be Correct . Mark them All )

Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ={0,1} Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}.Then L isRecursivel...

PEKKA

615 views

PEKKA asked Dec 5, 2016

0 votes

1 answer

33

Calicut Gate Academy Test Series | TOC
L={ambnckdl | (n-k ) is odd only if (m-l) is odd , m,n,k,l >=0 } is best fit under which language class RL DCFL CFL CSL

L={ambnckdl | (n-k ) is odd only if (m-l) is odd , m,n,k,l >=0 } is best fit under which language classRLDCFLCFLCSL

PEKKA

339 views

PEKKA asked Dec 5, 2016

1 votes

2 answers

34

Virtual Gate Test Series: Theory Of Computation - Turing Machine
Consider the following two decision problems Whether a Turing machine takes more than $481$ steps on input $\epsilon?$ Whether a Turing machine accepts the null string $\epsilon?$ Which of the following statements is true$?$ ... undecidable but $B$ is decidable Both $A$ and $B$ are decidable Both $A$ and $B$ are undecidable

Consider the following two decision problemsWhether a Turing machine takes more than $481$ steps on input $\epsilon?$Whether a Turing machine accepts the null string $\ep...

Hradesh patel

511 views

Hradesh patel asked Oct 7, 2016

1 votes

1 answer

35

Virtual Gate Test Series: Theory Of Computation - Regular Languages

Hradesh patel

359 views

Hradesh patel asked Oct 6, 2016

2 votes

2 answers

36

Virtual Gate Test Series: Theory Of Computation - Decidability
Here My explanation is : I. We run TM for 1,2,3,4,5....n if it stops in any of these then yes otherwise no II. We run TM for n steps if it stops yes otherwise no III. We run TM for n, n+1, n+2.... ... can say yes but if do not halt we can't say anything because we have to run it infinite number of times Is my explanation correct?

Here My explanation is :I. We run TM for 1,2,3,4,5....n if it stops in any of these then yes otherwise noII. We run TM for n steps if it stops yes otherwise noIII. We run...

Sumit1311

860 views

Sumit1311 asked Jan 22, 2016

1 votes

1 answer

37

CMI2011-A-09
You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your laptop? Turing machine Linear bounded automaton Pushdown automaton Finite state automaton

You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most...

go_editor

1.1k views

go_editor asked May 19, 2016

3 votes

1 answer

38

Virtual Gate Test Series: Theory Of Computation - Arbitrary Languages
Let $L_1$ and $L_2$ be two arbitrary languages, choose incorrect statement(s) $\text{if}\; L_1.L_2\;\text{ is regular then }L_2.L_1\;\text{ is also regular.}$ ... (\ denotes set difference) Only (i) (i) and (ii) (ii) and (iii) All

Let $L_1$ and $L_2$ be two arbitrary languages, choose incorrect statement(s)$\text{if}\; L_1.L_2\;\text{ is regular then }L_2.L_1\;\text{ is also regular.}$$L_1 = L_2 \;...

sourav.

734 views

sourav. asked Feb 3, 2016

0 votes

1 answer

39

Virtual Gate Test Series: Theory Of Computation - Decidable Language
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$ (C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$ (D) $L^R$ is decidable

$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$(C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$(D) $L^R$ is decidable

learncp

832 views

learncp asked Jan 26, 2016

0 votes

1 answer

40

Virtual Gate Test Series: Theory Of Computation - Undecidability

sourav.

337 views

sourav. asked Feb 3, 2016

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