Recent questions and answers in Theory of Computation / GATE Overflow for GATE CSE

which if the following statement is True for every set?a. $\exists$ a equivalence class that is also a partition set.b. Every equivalence relation on a set defines a part...

RahulVerma3

49 views

RahulVerma3 asked Apr 12

0 votes

0 answers

5

Context Free language sample question
Give a context-free grammar for each of the following languages. Consider, Σ={0,1}. A. The language of strings that start with 1 B. The language of strings of the form WWR C. The language of strings that contain the substring 001 D. The language {0n10n where n ≥ 0} E. ... i, j ≥ 0} J. The language {1i01j | j is a multiple of four or i = 3 + 2j where i, j ≥ 0}

Give a context-free grammar for each of the following languages. Consider, Σ={0,1}.A. The language of strings that start with 1B. The language of strings of the form WWR...

dazeeee

66 views

dazeeee asked Apr 3

0 votes

0 answers

6

Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$? assuming $ at the end and begining of the input tape

Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape

RahulVerma3

52 views

RahulVerma3 asked Apr 2

0 votes

3 answers

7

Made easy, theory of computaion, Easy level edition 2022
Please explain me why the 4th option is also a true statement.

Please explain me why the 4th option is also a true statement.

Bhaskar_Saini

188 views

Bhaskar_Saini answered Mar 29

12 votes

5 answers

8

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

AjithAddala

7.1k views

AjithAddala answered Mar 25

1 votes

3 answers

9

GATE CSE 2024 | Set 2 | Question: 52
Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}...

Mihir L. Agrawal

2.0k views

Mihir L. Agrawal answered Mar 23

0 votes

0 answers

10

THEORY OF AUTOMATA ASSIGNMENT # 1 1. Write regular expressions and draw NFA for the following languages over the alphabet Σ = {a, b}: a. All strings that do not end with aa. b. All strings that contain an even number of b’s c. All strings that contain atleast two a’s or exactly two b’s d. All strings that ends with double letters (aa or bb) e. All strings that does not ends with double letter.(can end with ab or ba)

Talha Riaz

99 views

Talha Riaz asked Mar 23

0 votes

1 answer

11

Set of binary strings starting with 11 and ending with 00. E.g., 1100,1110100 ,1100100

prasantkr.singh

75 views

prasantkr.singh answered Mar 22

1 votes

2 answers

12

GATE CSE 2024 | Set 2 | Question: 31
Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$? $(00)^{*}+1(11)^{*}$ $0^{*}+\left(1+0(00)^{*}\right)(11)^{*}$ $(00)^{*}+\left(1+(00)^{*}\right)(11)^{*}$ $0^{+}+1(11)^{*}+0(11)^{*}$

Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below.Which one of the following regular expressions represents the la...

ashwinsuthar1

2.4k views

ashwinsuthar1 answered Mar 19

0 votes

1 answer

13

Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.

Mrityudoot

114 views

Mrityudoot answered Mar 16

0 votes

0 answers

14

Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non- ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?

There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself a...

dopq12

96 views

dopq12 asked Mar 5

2 votes

3 answers

15

GATE CSE 2024 | Set 1 | Question: 51
Consider the following two regular expressions over the alphabet $\{0,1\}$ : $r= 0^{*}+1^{*}$ $s = 01^{*} + 10^{*}$ The total number of strings of length less than or equal to $5$, which are neither in $r$ nor in $s$, is ________.

Consider the following two regular expressions over the alphabet $\{0,1\}$ :$r= 0^{*}+1^{*}$$s = 01^{*} + 10^{*}$The total number of strings of length less than or equal ...

jvishal

1.8k views

jvishal answered Mar 2

0 votes

2 answers

16

#Convert the NFA in to equivalent R.E.

m1_lan____

173 views

m1_lan____ answered Feb 26

0 votes

0 answers

17

#toc

Çșȇ ʛấẗẻ

90 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

0 answers

18

Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR,∑,δR,q0R,FR).

Vedantthakkar

143 views

Vedantthakkar asked Feb 24

0 votes

0 answers

19

Pumping Lemma
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and explain why pumping it leads to a contradiction. {aaabnan∣n≥0} {ww∣w∈Σ∗}

Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...

jg662

83 views

jg662 asked Feb 22

2 votes

1 answer

20

GATE CSE 2024 | Set 2 | Question: 42
Consider a context-free grammar $\text{G}$ with the following $3$ rules. \[ S \rightarrow a S, S \rightarrow a S b S , S \rightarrow c \] Let $w \in L(G)$. Let $ n_{a}(w), n_{b}(w), n_{c}(w) $ denote the number of times $a, b, c$ occur in $w$, respectively. Which of ... $n_{a}(w)>n_{c}(w)-2$ $n_{c}(w)=n_{b}(w)+1$ $n_{c}(w)=n_{b}(w) * 2$

Consider a context-free grammar $\text{G}$ with the following $3$ rules.\[S \rightarrow a S, S \rightarrow a S b S , S \rightarrow c\]Let $w \in L(G)$...

liontig37

1.8k views

liontig37 answered Feb 22

0 votes

0 answers

21

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement. a. {0"1"0"| m, n 2 0} b. (0"1"| m ‡ n) c. (w| w € {0,1)* is not a palindrome) d. (wtw| w,t € (0,1)*)

krishan_rathi

154 views

krishan_rathi asked Feb 21

1 votes

1 answer

22

GATE CSE 2024 | Set 1 | Question: 40
Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. ... $4$ are distinguishable in $M$ States $2$ and $5$ are distinguishable in $M$ Any string $w$ with $n_0(w)=n_1(w)$ is in $L(M)$

Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\...

phaniphani

2.4k views

phaniphani answered Feb 16

1 votes

1 answer

23

GATE CSE 2024 | Set 1 | Question: 13
Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE? $L_1=L_2$ if and only if $L_1 \cap \overline{L_2}=\phi$ $L_1 \cup L_3$ is not regular $\overline{L_3}$ is not regular $\overline{L_1} \cup \overline{L_2}$ is regular

Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular.Which of the following statements is/are always TRUE?$L_1=L_2$ if and only if $L_1 \c...

malaviya_parth

2.7k views

malaviya_parth answered Feb 16

2 votes

2 answers

24

GATE CSE 2024 | Set 2 | Question: 12
Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below? $0^{*} 1\left(0+10^{*} 1\right)^{*}$ $0^{*}\left(10^{*} 11\right)^{*} 0^{*}$ $0^{*} 1\left(010^{*} 1\right)^{*} 0^{*}$ $0\left(1+0^{*} 10^{*} 1\right)^{*} 0^{*}$

Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?$0^{*} 1\left(0+10^{*} 1\right)^{*}$$0^{...

Deepak Poonia

2.5k views

Deepak Poonia answered Feb 16

0 votes

1 answer

25

Not Regular language [find out]
Why is C is regular as it non regular as? Please help me with this confusion

Why is C is regular as it non regular as?Please help me with this confusion

bluesta

218 views

bluesta answered Feb 15

0 votes

1 answer

26

Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.{w| w starts with 0 and has odd length, or starts with 1 and has even length}

Sujith48

134 views

Sujith48 answered Feb 15

0 votes

0 answers

27

Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}.{w| w does not contain the substring ab} {w| w does not contain the substring baba} {w| w contains neither the substrings ab nor ba} {w| w is any string not in a∗ ∪ b∗ } ( ∪ is the union )

Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of ...

rania

114 views

rania asked Feb 14

0 votes

3 answers

28

michael sipser chp 1, 3rd edition, Q 12 , dfa
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab } give a DFA with Five states that recognizes D and a regular expression that generates D.

let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab }give a DFA with Five states that recognizes D and a regular express...

cherry348

3.7k views

cherry348 answered Feb 12

3 votes

1 answer

29

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 32
Which of the following sets has the greatest cardinality? The set of real numbers R The set of all functions from R to {0,1} The set of all finite subsets of natural numbers The set of all finite-length binary strings

Which of the following sets has the greatest cardinality?The set of real numbers RThe set of all functions from R to {0,1}The set of all finite subsets of natural numbers...

Bharadwaja1557

455 views

Bharadwaja1557 answered Feb 7

5 votes

1 answer

30

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 64
Which of the following languages are Turing-recognizable? A. $\{\langle M\rangle \mid M$ is a (deterministic) Turing machine and $M$ accepts 010$\}$. B. $\{\langle M\rangle \mid M$ is a nondeterministic Turing machine and $M$ accepts 010 ... $\left\{\langle M\rangle \mid M\right.$ is a Turing machine and $\left.L(M)=\Sigma^*\right\}$.

Which of the following languages are Turing-recognizable?A. $\{\langle M\rangle \mid M$ is a (deterministic) Turing machine and $M$ accepts 010$\}$.B. $\{\langle M\rangle...

Prabhas

509 views

Prabhas answered Feb 6

3 votes

1 answer

31

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 35
Which of the following strings are a member of the language described by the regular expression $\left(a^* {b} {a}^* b a^* b {a}^*\right)^*$ $b b b b$ $bbaaabb$ $bbaaabbbabb$ $b b a b b b a b$

Which of the following strings are a member of the language described by the regular expression $\left(a^* {b} {a}^* b a^* b {a}^*\right)^*$$b b b b$$bbaaabb$$bbaaabbbabb...

shubhsy1729

558 views

shubhsy1729 answered Feb 6

4 votes

0 answers

32

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 31
DeMorgan's Laws ensure that Closure under intersection and complementation imply closure under union. Closure under intersection and union imply closure under complementation. Closure under union and complementation imply closure ... Closure under any two of union, intersection, and complementation implies closure under all three.

DeMorgan’s Laws ensure thatClosure under intersection and complementation imply closure under union.Closure under intersection and union imply closure under complementa...

GO Classes

331 views

GO Classes asked Feb 5

4 votes

0 answers

33

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 65
Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$ $L^{\star}$ is infinite. $L$ is accepted by some DFA if and only if $L$ is accepted by some NFA. If $\mathrm{L}$ is the ... $\mathrm{L}$ is undecidable. If $\mathrm{L}$ is the union of two decidable languages, then $\mathrm{L}$ is decidable.

Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$$L^{\star}$ is infinite.$L$ is accepted by some DFA if and only if $L$ is ac...

GO Classes

615 views

GO Classes asked Feb 5

53 votes

3 answers

34

GATE CSE 2006 | Question: 30
For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$Which ... following statements is true? $L$ is recursively enumerable, but not recursive $L$ is recursive, but not context-free $L$ is context-free, but not regular $L$ is regular

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let$$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod ...

Amoljadhav

7.7k views

Amoljadhav answered Feb 3

0 votes

1 answer

35

Why is L1 not DCFL?

Mrityudoot

110 views

Mrityudoot answered Jan 28

6 votes

1 answer

36

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 23
Which of the following statements is/are false? If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ is not ambiguous. For every number $n$ ... s a $10$-state NFA that accepts $\text{L}$ then there's a $100$-state DFA that accepts $\mathrm{L}$.

Which of the following statements is/are false?If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ is not ambiguous.For every number $n$...

GO Classes

634 views

GO Classes answered Jan 28

6 votes

1 answer

37

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 24
Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then the maximum possible cardinality of $\text{L(M)}$ is __________.

Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then ...

GO Classes

558 views

GO Classes answered Jan 28

5 votes

1 answer

38

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55
Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$. Which of the following sets is not ... machine halts on the input $m$. The set of $n$ such that all Turing machines halt on the input $n$.

Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$....

GO Classes

500 views

GO Classes answered Jan 28

7 votes

1 answer

39

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 56
For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual power of strings) and $x^{\downarrow m}=x_1^m \cdots x_n^m$. For empty ... $\left\{(a b c)^{\downarrow n} \mid n \geq 0\right\}$

For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual power of...

GO Classes

474 views

GO Classes answered Jan 28

8 votes

1 answer

40

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 57
Consider a pushdown automaton (PDA) with two control states $Q=\{q 1, q 2\}$, start state $q 1$, input alphabet $\Sigma=\{a, b\}$, stack alphabet $\Gamma=\{\perp, a\}$ (where $\perp$ is the start symbol ... $21$ accepted by the above pushdown automaton is _________.

Consider a pushdown automaton (PDA) with two control states $Q=\{q 1, q 2\}$, start state $q 1$, input alphabet $\Sigma=\{a, b\}$, stack alphabet $\Gamma=\{\perp, a\}$ (w...

GO Classes

596 views

GO Classes answered Jan 28

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