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

62 votes

9 answers

21

GATE CSE 2010 | Question: 41
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$? $n-1$ $n$ $n+1$ $2^{n-1}$

Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automati...

go_editor

24.0k views

go_editor asked Sep 30, 2014

31 votes

4 answers

22

GATE CSE 2022 | Question: 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below? $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$ $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$ $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$ $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$

Which one of the following regular expressions correctly represents the language of the finite automaton given below?$ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$$(ab^{\ast...

Arjun

17.8k views

Arjun asked Feb 15, 2022

32 votes

3 answers

23

GATE IT 2006 | Question: 31
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA? $\{a^nb^nc^n \mid n ≥ 0\}$ $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$ $\{a^nb^n \mid n ≥ 0\}$ $\{a^mb^n \mid m, n ≥ 0\}$

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?$\{a^nb^nc^n \mid n ≥ 0\}$$\{a^lb^mc^n \mid ...

Ishrat Jahan

18.1k views

Ishrat Jahan asked Oct 31, 2014

39 votes

4 answers

24

GATE CSE 1998 | Question: 2.5
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is $2$ $5$ $8$ $3$

Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$...

Kathleen

17.4k views

Kathleen asked Sep 25, 2014

18 votes

7 answers

25

GATE CSE 2020 | Question: 51
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________

Consider the following language.$L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$The minimum number of states in DFA that ...

Arjun

13.5k views

Arjun asked Feb 12, 2020

35 votes

4 answers

26

GATE CSE 2019 | Question: 34
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$ S2: Set of all syntactically valid C programs S3: Set of all languages over the alphabet $\{0,1\}$ S4: Set of all non-regular languages over the alphabet $\{ 0,1 \}$ Which of the above sets are uncountable? S1 and S2 S3 and S4 S2 and S3 S1 and S4

Consider the following sets:S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$S2: Set of all syntactically valid C programsS3: Set of all langua...

Arjun

13.1k views

Arjun asked Feb 7, 2019

68 votes

10 answers

27

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^*$

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 express...

go_editor

22.4k views

go_editor asked Sep 30, 2014

24 votes

3 answers

28

GATE CSE 2020 | Question: 7
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s? $((0+1)^*1(0+1)^*1)^*10^*$ $(0^*10^*10^*)^*0^*1$ $10^*(0^*10^*10^*)^*$ $(0^*10^*10^*)^*10^*$

Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s?$((0+1)^*1(0+1)^*1)^*10^*$$(0^*10^*10^*)^*0^*1$$10^*...

Arjun

23.7k views

Arjun asked Feb 12, 2020

79 votes

3 answers

29

GATE CSE 2016 Set 2 | Question: 42
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false

Consider the following two statements:If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$.There exists a regular languag...

Akash Kanase

25.6k views

Akash Kanase asked Feb 12, 2016

56 votes

4 answers

30

GATE CSE 1998 | Question: 1.10
Which of the following set can be recognized by a Deterministic Finite state Automaton? The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary The numbers $1, 2, 4, 8,\dots 2^n, \dots$ written in unary The set of binary string in which the number of zeros is the same as the number of ones. The set $\{1, 101, 11011, 1110111, \dots\}$

Which of the following set can be recognized by a Deterministic Finite state Automaton?The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binaryThe numbers $1, 2, 4, 8...

Kathleen

15.6k views

Kathleen asked Sep 25, 2014

14 votes

5 answers

31

GATE CSE 2023 | Question: 29
Consider the context-free grammar $G$ below \[ \begin{array}{l} S \rightarrow a S b \mid X \\ X \rightarrow a X \mid X b \mid a \mid b, \end{array} \] where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non- ... $G$ is $a^{\ast} b^{\ast}(a+b)$ The language generated by $G$ is not a regular language

Consider the context-free grammar $G$ below\[\begin{array}{l}S \rightarrow a S b \mid X \\X \rightarrow a X \mid X b \mid a \mid b,\end{array}\]where $S$ and $X$ are non-...

admin

9.1k views

admin asked Feb 15, 2023

57 votes

4 answers

32

GATE CSE 2016 Set 1 | Question: 18
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s? $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$ $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$ $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$ $00(0+1)^*11 +11(0+1)^*00$

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s?$(0+1 )^ *001...

Sandeep Singh

20.8k views

Sandeep Singh asked Feb 12, 2016

43 votes

7 answers

33

GATE CSE 2012 | Question: 24
Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive? $1, 2, 3, 4$ $1, 2$ $2, 3, 4$ $3, 4$

Which of the following problems are decidable?Does a given program ever produce an output?If $L$ is a context-free language, then, is $\bar{L}$ also context-free?If $L$ i...

Arjun

15.7k views

Arjun asked Sep 25, 2014

61 votes

7 answers

34

GATE CSE 2003 | Question: 50
Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is $1$ $5$ $7$ $8$

Consider the following deterministic finite state automaton $M$.Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $...

Kathleen

15.0k views

Kathleen asked Sep 17, 2014

12 votes

5 answers

35

GATE CSE 2023 | Question: 30
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ ... $\left.0 \leq n\right\}$ $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$

Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}...

admin

7.1k views

admin asked Feb 15, 2023

6 votes

2 answers

36

GATE CSE 2022 | Question: 13
Which of the following statements is/are $\text{TRUE}?$ Every subset of a recursively enumerable language is recursive. If a language $\textit{L}$ and its complement $\overline{\textit{L}}$ are both recursively enumerable, then $\textit{L}$ must be recursive. ... $\textit{L}_{1} \cap \textit{L}_{2}$ must be deterministic context-free.

Which of the following statements is/are $\text{TRUE}?$Every subset of a recursively enumerable language is recursive.If a language $\textit{L}$ and its complement $\over...

Arjun

15.4k views

Arjun asked Feb 15, 2022

86 votes

4 answers

37

GATE CSE 2017 Set 1 | Question: 39
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an ... $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.

Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if th...

Arjun

18.5k views

Arjun asked Feb 14, 2017

26 votes

5 answers

38

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)^*$

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...

Arjun

12.4k views

Arjun asked Feb 18, 2021

70 votes

4 answers

39

GATE CSE 2003 | Question: 54
Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a ... $L'$ is recursively enumerable, but $ L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable

Define languages $L_0$ and $L_1$ as follows :$L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $$L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts o...

Arjun

24.2k views

Arjun asked Sep 8, 2014

50 votes

5 answers

40

GATE CSE 2016 Set 2 | Question: 43
Consider the following languages: $L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$ $L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$ Which one of the following is TRUE? Both $L_{1}$ and $L_{2}$ are context-free. $L_{1}$ is context ... $L_{2}$ is context-free while $L_{1}$ is not context-free. Neither $L_{1}$ nor $L_{2}$ is context-free.

Consider the following languages:$L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$$L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$Which one of the following is TRUE?Bot...

Akash Kanase

21.5k views

Akash Kanase asked Feb 12, 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