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

2 votes

3 answers

81

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.9k views

Arjun asked Feb 16

40 votes

9 answers

82

GATE CSE 1991 | Question: 17,b
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?

Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many s...

Kathleen

13.7k views

Kathleen asked Sep 12, 2014

33 votes

7 answers

83

GATE CSE 2009 | Question: 15
Which one of the following languages over the alphabet $\{0,1\}$ is described by the regular expression: $(0+1)^*0(0+1)^*0(0+1)^*$? The set of all strings containing the substring $\text{00}$ ... containing at least two $\text{0}$'s The set of all strings that begin and end with either $\text{0}$ or $\text{1}$

Which one of the following languages over the alphabet $\{0,1\}$ is described by the regular expression: $(0+1)^*0(0+1)^*0(0+1)^*$?The set of all strings containing the s...

Kathleen

15.0k views

Kathleen asked Sep 22, 2014

3 votes

2 answers

84

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

GO Classes

589 views

GO Classes asked Feb 5

32 votes

1 answer

85

GATE CSE 2021 Set 2 | Question: 36
Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true

Consider the following two statements about regular languages:$S_1$: Every infinite regular language contains an undecidable language as a subset.$S_2$:...

Arjun

12.1k views

Arjun asked Feb 18, 2021

41 votes

7 answers

86

GATE CSE 1998 | Question: 1.12
The string $1101$ does not belong to the set represented by $110^*(0 + 1)$ $1(0 + 1)^*101$ $(10)^*(01)^*(00 + 11)^*$ $(00 + (11)^*0)^*$

The string $1101$ does not belong to the set represented by$110^*(0 + 1)$$1(0 + 1)^*101$$(10)^*(01)^*(00 + 11)^*$$(00 + (11)^*0)^*$

Kathleen

23.3k views

Kathleen asked Sep 25, 2014

64 votes

4 answers

87

GATE CSE 2003 | Question: 51
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ is not ambiguous There ... $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$

Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$Which of the following...

Kathleen

17.7k views

Kathleen asked Sep 17, 2014

38 votes

5 answers

88

GATE CSE 2016 Set 2 | Question: 16
The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.

The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.

Akash Kanase

15.9k views

Akash Kanase asked Feb 12, 2016

68 votes

7 answers

89

GATE CSE 2012 | Question: 46
Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially ...

Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $1000...

Arjun

14.4k views

Arjun asked Sep 29, 2014

47 votes

4 answers

90

GATE IT 2007 | Question: 71
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which of the following non-deterministic finite automata recognizes the language defined by the regular expression $R$? Edges labeled $\lambda $ denote transitions on the empty string.

Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which of the following non-deterministic finite automata recognizes the language defined by the regular...

Ishrat Jahan

8.3k views

Ishrat Jahan asked Oct 30, 2014

1 votes

0 answers

91

How is "All strings {0,1} of length five or more in which the third symbol from the right end is different from the leftmost symbol" solved?

How is "All strings {0,1} of length five or more in which the third symbol from the right end is different from the leftmost symbol" solved? Answer Follow·1 Request ...

paressep28

66 views

paressep28 asked Apr 25

1 votes

1 answer

92

#TOC regular expression
what will be the regular expression of this DFA using Arden's theorem

what will be the regular expression of this DFA using Arden's theorem

prabhath challa

74 views

prabhath challa asked Apr 18

0 votes

0 answers

93

DFA construction
Design a DFA (Deterministic Finite Automaton) that recognizes the language L defined follows: L= {w -> {a, b}* | every a in w is immediately followed by bb}

Design a DFA (Deterministic Finite Automaton) that recognizes the language L defined follows: L= {w - {a, b}* | every a in w is immediately followed by bb}

rdrd44

19 views

rdrd44 asked 14 hours ago

0 votes

0 answers

94

Regular Expresssion And NFA
In certain programming languages, comments appear between delimiters such as (* and ) . Let C be the language of all valid delimited comment strings. Such a string in C must begin with ( and end with *) but have no intervening *) . For simplicity, assume the ... b, (, *)}. (a) Provide an NFA that recognizes language C . (b) Present a regular expression that generates C.

In certain programming languages, comments appear between delimiters such as (* and ) . Let C be the language of all valid delimited comment strings. Such a string in C...

rdrd44

18 views

rdrd44 asked 14 hours ago

0 votes

2 answers

95

Regular language
Can anyone explain how we can write this regular language for the following diagram ?(in depth)

Can anyone explain how we can write this regular language for the following diagram ?(in depth)

programmer1218

149 views

programmer1218 asked Apr 11

30 votes

6 answers

96

GATE CSE 1996 | Question: 1.8
Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string). $(00)^ * (\varepsilon +0)$ $(00)^*$ $0^*$ $0(00)^*$ (i) and (ii) (ii) and (iii) (i) and (iii) (iii) and (iv)

Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string).$(00)^ * (\varepsilon +0)$$(00)^*$$0^*$$0(00)^*$(i) and (ii)(ii) a...

Kathleen

10.4k views

Kathleen asked Oct 9, 2014

54 votes

4 answers

97

GATE CSE 2014 Set 1 | Question: 36
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III

Which of the regular expressions given below represent the following DFA?$0^*1(1+00^*1)^* $$0^*1^*1+11^*0^*1 $$(0+1)^*1$I and II onlyI and III onlyII and III onlyI, II an...

go_editor

19.1k views

go_editor asked Sep 28, 2014

0 votes

1 answer

98

#unacademyDPP

4nm01_

70 views

4nm01_ asked Apr 9

0 votes

3 answers

99

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

212 views

RahulVerma3 asked Mar 27

6 votes

1 answer

100

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

582 views

GO Classes asked 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