Recent questions tagged theory-of-computation / GATE Overflow for GATE CSE

0 votes

0 answers

31

how is this option A and B correct, L1 is definitely regular but L2 is not and is CSL?

pcla

5 views

pcla asked Jan 27

0 votes

1 answer

32

Why is L1 not DCFL?

pcla

109 views

pcla asked Jan 27

1 votes

1 answer

33

Gate CSE Made Easy Test Series
Construct a minimal finite state automation that accepts the language over {0, 1} of all strings that contain neither the substring 00 nor the substring 11. What is the number of states in this machine? For this question when we draw the DFA there ... and NFA contains 3 states minimum. So according to question what shall be the answer for this question? 3 or 4? Why?

“Construct a minimal finite state automation that accepts the language over {0, 1} of all strings that contain neither the substring 00 nor the substring 11. What is th...

abhiyodayapandey

235 views

abhiyodayapandey asked Jan 21

3 votes

1 answer

34

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 15
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$. $\emptyset$ $\{a\}^*$ $\{a\}$ $\{\varepsilon\}$

Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$.$\emptyset$$\{a\}^*$$...

GO Classes

471 views

GO Classes asked Jan 21

2 votes

1 answer

35

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 42
Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensures that $L_1 \cap L_2$ ... and $\left.m \geq 0\right\}$ $L_2=\left\{a^k b^{2 k} c^{2 k} \mid k \geq 0\right\}$

Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensu...

GO Classes

516 views

GO Classes asked Jan 21

8 votes

1 answer

36

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true? If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite ... $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite.

Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true?If $\text{D}$ accepts some string of length $n$, the...

GO Classes

654 views

GO Classes asked Jan 21

3 votes

2 answers

37

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 44
Which of the following statements is/are false? Let $\text{A}$ and $\text{B}$ be sets of languages over some fixed alphabet $\Sigma$, with $\text{A} \subseteq \text{B}$. If $\text{A}$ is closed under some operation $\text{P},$ then ... $\mathrm{L} 2$ $\subseteq \mathrm{L} 1$, then $\mathrm{L} 2$ is decidable.)

Which of the following statements is/are false?Let $\text{A}$ and $\text{B}$ be sets of languages over some fixed alphabet $\Sigma$, with $\text{A} \subseteq \text{B}$. I...

GO Classes

557 views

GO Classes asked Jan 21

5 votes

2 answers

38

Which one of the following context-free grammars is unambiguous? (Note that $a, b, c,(,),+$ are terminals, $S, X, Y$ are nonterminals, and the start symbol in each case i...

GO Classes

639 views

GO Classes asked Jan 13

3 votes

1 answer

39

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 61
Which of the following is/are undecidable? $L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\}$. $\{\langle M\rangle \mid M$ ... $\}$ $L=\{\langle M\rangle \mid M$ is a DFA and $L(M)$ is uncountable $\}$

Which of the following is/are undecidable?$L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\...

GO Classes

567 views

GO Classes asked Jan 13

4 votes

2 answers

40

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 62
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful transition is possible for the given symbol. Note that when encountering a $b$ in state ... $\mathrm{abbb}^+\mathrm{c}^+\mathrm{c}$ $a b^* b b(c c)^+$

Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful ...

GO Classes

346 views

GO Classes asked Jan 13

4 votes

1 answer

41

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 63
This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpreted, in the natural way, as the numbers $1$ and $-1,$ in ... $\text{L}_1$ Only $\text{L}_2$ Both None

This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpr...

GO Classes

566 views

GO Classes asked Jan 13

4 votes

1 answer

42

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 64
Which of the following statements about Turing machines is false? For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of $L$. For any grammar $G$ ... Turing machine $A$ which can simulate the behaviour of any given Turing machine $B$ on any given finite input.

Which of the following statements about Turing machines is false?For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of...

GO Classes

537 views

GO Classes asked Jan 13

6 votes

1 answer

43

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 65
Consider the following non-deterministic pushdown automaton. The input alphabet is $\{a, b\}$, the stack alphabet is $\{*, a, b\}$, and the initial stack symbol is $*$. Acceptance is by empty stack. We use $x$ as a variable that ranges over ... and $a, a: a a$ and $a, b: a b$. How many strings of length $12$ are accepted by this NPDA?

Consider the following non-deterministic pushdown automaton. The input alphabet is $\{a, b\}$, the stack alphabet is $\{*, a, b\}$, and the initial stack symbol is $*$. A...

GO Classes

709 views

GO Classes asked Jan 13

0 votes

1 answer

44

What is correct approach to solve such questions ?

ENTJ007

93 views

ENTJ007 asked Jan 12

1 votes

1 answer

45

Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?

If it’s DCFL then also construct the DPDA ?

vedantk

150 views

vedantk asked Jan 10

0 votes

1 answer

46

#self doubt
a^n ww^r a^n .. (n>=0, w belongs to (a,b)*) Can someone please explain the flow how we will process the language in CFL.

a^n ww^r a^n .. (n>=0, w belongs to (a,b)*)Can someone please explain the flow how we will process the language in CFL.

Dknights

88 views

Dknights asked Jan 8

0 votes

1 answer

47

ISRO 2024
Consider the context free grammar $G$ for below for the arithmetic expressions: $E \rightarrow E + E | E \times E | \text{id}$ Which of the follosing statements is TRUE: The string $\text{id} + \text{id} \times \text{id}$ has no parse tree according to $G$ The ... tree according to $G$ The string $\text{id} + \text{id} \times \text{id}$ has more than two parse tree according to $G$

Consider the context free grammar $G$ for below for the arithmetic expressions:$E \rightarrow E + E | E \times E | \text{id}$Which of the follosing statements is TRUE:Th...

Ramayya

256 views

Ramayya asked Jan 7

1 votes

0 answers

48

ISRO 2024
Consider the context-free grammer $G$ below. There $S$ is the starting non terminal symbol, while $a$ and $b$ are terminal symbols. $S \rightarrow aaSb | T$ $T \rightarrow Tb | a$ Which of the following statments is true about the language $L(G)$ generated by $G$? ... $aaaabb$ does not $aaaabb$ belongs to $L(G)$ but $aabbaabb$ does not $aaabb$ belongs to $L(G)$ but $aaaaabbb$ does not

Consider the context-free grammer $G$ below. There $S$ is the starting non terminal symbol, while $a$ and $b$ are terminal symbols.$S \rightarrow aaSb | T$$T \rightarrow ...

Ramayya

200 views

Ramayya asked Jan 7

2 votes

1 answer

49

ISRO 2024
Which f the following statements is FALSE? The intersection of a regular language and a context-free language is context=free The intersection of a regular language and context-free language is regular The union of two context-free languages is context-free The union of two regular languages is regular

Which f the following statements is FALSE?The intersection of a regular language and a context-free language is context=freeThe intersection of a regular language and con...

Ramayya

181 views

Ramayya asked Jan 7

0 votes

0 answers

50

ISRO 2024
which of the following statements is NOT true? If a language is recursive it complement is recursive If a language is recursive its complement is recursively enumerable If a language and its complement are recursively enumerable it is recursive If a language is recursively enumerable its complement is also recursively enumerable

which of the following statements is NOT true?If a language is recursive it complement is recursiveIf a language is recursive its complement is recursively enumerableIf a...

Ramayya

145 views

Ramayya asked Jan 7

0 votes

1 answer

51

Find the number of final states in DFA that recognizes L, where L= {w1a w2:|w1|≥3,|w2|≤5}, ∑={a, b} and w1, w2 ∈ ∑ * ______

Hritik1204

309 views

Hritik1204 asked Jan 5

0 votes

1 answer

52

#Applied Course
Please explain this.

Please explain this.

Dknights

110 views

Dknights asked Jan 4

1 votes

0 answers

53

Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language

L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t ...

amitarp818

238 views

amitarp818 asked Dec 28, 2023

0 votes

0 answers

54

Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?

Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?

raj_uddeshya157

77 views

raj_uddeshya157 asked Dec 27, 2023

0 votes

2 answers

55

#self doubt
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid

MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid

Dknights

171 views

Dknights asked Dec 23, 2023

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