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

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

72 views

dazeeee asked Apr 3

0 votes

0 answers

5

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

54 views

RahulVerma3 asked Apr 2

0 votes

3 answers

6

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.

RahulVerma3

193 views

RahulVerma3 asked Mar 27

0 votes

0 answers

7

Regular Expresssion And NFA (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 ... with double letters (aa or bb) e. All strings that does not ends with double letter.(can end with ab or ba)

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

Talha Riaz

112 views

Talha Riaz asked Mar 23

0 votes

1 answer

8

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

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

hasina ali

90 views

hasina ali asked Mar 21

0 votes

1 answer

9

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

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

utsav22222

131 views

utsav22222 asked Mar 15

0 votes

1 answer

10

Prove that n! = Ω(n^100)

wtquevb123

96 views

wtquevb123 asked Mar 14

0 votes

0 answers

11

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

99 views

dopq12 asked Mar 5

0 votes

0 answers

12

#toc

Çșȇ ʛấẗẻ

91 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

2 answers

13

#Convert the NFA in to equivalent R.E.

Çșȇ ʛấẗẻ

180 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

0 answers

14

#TOC

Çșȇ ʛấẗẻ

57 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

0 answers

15

CFL and regular language
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).

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

Vedantthakkar

161 views

Vedantthakkar asked Feb 24

0 votes

0 answers

16

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

87 views

jg662 asked Feb 22

0 votes

0 answers

17

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

156 views

krishan_rathi asked Feb 21

2 votes

2 answers

18

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

Arjun

2.6k views

Arjun asked Feb 16

1 votes

2 answers

19

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

Arjun

2.4k views

Arjun asked Feb 16

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

Arjun

1.8k views

Arjun asked Feb 16

1 votes

3 answers

21

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

Arjun

2.1k views

Arjun asked Feb 16

1 votes

1 answer

22

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

Arjun

2.8k views

Arjun asked Feb 16

1 votes

1 answer

23

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^{\...

Arjun

2.5k views

Arjun asked Feb 16

2 votes

3 answers

24

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

Arjun

1.8k views

Arjun asked Feb 16

0 votes

0 answers

25

Regular expression to finite automata

Çșȇ ʛấẗẻ

224 views

Çșȇ ʛấẗẻ asked Feb 15

0 votes

0 answers

26

DFA construction
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}. 1- {w| w does not contain the substring ab} 2- {w| ... neither the substrings ab nor ba} 4- {w| w is any string not in $a^{*}\cup 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 a...

rania

123 views

rania asked Feb 14

0 votes

1 answer

27

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

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

rania

146 views

rania asked Feb 14

4 votes

0 answers

28

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

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

GO Classes

456 views

GO Classes asked Feb 5

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