Search results for minimal-state-automata / GATE Overflow for GATE CSE

19 votes

3 answers

1

How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA

The alphabets are a and b.Construct a DFA

Gourab_Classic

109k views

Gourab_Classic asked Mar 14, 2016

54 votes

15 answers

2

GATE CSE 2017 Set 1 | Question: 22
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .

Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-...

Arjun

29.3k views

Arjun asked Feb 14, 2017

93 votes

8 answers

3

GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$

Rucha Shelke

34.3k views

Rucha Shelke asked Sep 22, 2014

57 votes

5 answers

4

GATE CSE 2019 | Question: 48
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... Consider the language $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______

Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$...

Arjun

20.3k views

Arjun asked Feb 7, 2019

62 votes

9 answers

5

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

39 votes

4 answers

6

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

65 votes

12 answers

7

GATE CSE 2015 Set 1 | Question: 52
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

makhdoom ghaya

17.2k views

makhdoom ghaya asked Feb 13, 2015

55 votes

5 answers

8

GATE CSE 2015 Set 3 | Question: 18
Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)? $4$ $5$ $6$ $8$

Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recogni...

go_editor

17.1k views

go_editor asked Feb 14, 2015

36 votes

6 answers

9

GATE CSE 2011 | Question: 45
A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below. Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?

A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below.Which of the following finite state machines is a valid minimal $\tex...

go_editor

10.8k views

go_editor asked Sep 29, 2014

9 votes

4 answers

10

GATE CSE 2023 | Question: 53
Consider the language $L$ over the alphabet $\{0,1\}$, given below: \[ L=\left\{w \in\{0,1\}^{*} \mid w \text { does not contain three or more consecutive } 1 \text { 's }\right\} . \] The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Consider the language $L$ over the alphabet $\{0,1\}$, given below:\[L=\left\{w \in\{0,1\}^{*} \mid w \text { does not contain three or more consecutive } 1 \text { 's }\...

admin

9.3k views

admin asked Feb 15, 2023

38 votes

5 answers

11

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

Akash Kanase asked Feb 12, 2016

62 votes

2 answers

12

GATE CSE 2011 | Question: 42
Definition of a language $L$ with alphabet $\{a\}$ is given as following.$ L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$What is the minimum number of states needed in a DFA to recognize $L$? $k+1$ $n+1$ $2^{n+1}$ $2^{k+1}$

Definition of a language $L$ with alphabet $\{a\}$ is given as following.$$ L = \left\{a^{nk} \mid k 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$$...

go_editor

17.5k views

go_editor asked Sep 29, 2014

36 votes

6 answers

13

GATE CSE 2015 Set 2 | Question: 53
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

go_editor

15.6k views

go_editor asked Feb 13, 2015

47 votes

9 answers

14

GATE CSE 2017 Set 2 | Question: 25
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \righ...

Madhav

16.5k views

Madhav asked Feb 14, 2017

0 votes

1 answer

15

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

312 views

Hritik1204 asked Jan 5

21 votes

2 answers

16

GATE CSE 1997 | Question: 70
Following is a state table for time finite state machine. ... . For example if states $X$ and $Y$ are equivalent then use $XY$ as the name for the equivalent state in the minimal machine).

Following is a state table for time finite state machine.$$\begin{array}{|l|ll|}\hline \textbf{Present State} & \textbf{Next State Output} \\ & \textbf{Input- 0} & \t...

go_editor

7.8k views

go_editor asked Oct 14, 2015

1 votes

1 answer

17

Minimal Finite Automata - Theory of Computation
Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts the given set is _____________? (kindly explain the approach to this problem)

Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts th...

stillhere

396 views

stillhere asked Sep 10, 2023

0 votes

2 answers

18

deadlocks and threads operating system
A system has 5 process and 3 resources (A, B, C). The maximum count of resources are (10, 5, 7). Consider the following table of resource allocation. MAX (A B C) Allocated (A B C) P0 7 5 3 0 1 0 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 ... these is a safe sequence in Question 13? P1, P3, P4 , P0, P2 only P2, P4, P3, P1, P0 only Both a and b None are safe sequences

A system has 5 process and 3 resources (A, B, C). The maximum count of resources are (10, 5, 7). Consider the following table of resource allocation. MAX(A B C)Alloc...

roopkathaaa

1.6k views

roopkathaaa asked Sep 2, 2023

0 votes

1 answer

19

deadlocks and threads operating system
State true or false. Deadlock detection is possible using the allocation and request matrices alone. A way to recover from deadlock is to take away the resource from one of the processes or to kill the process itself. Banker's algorithm is ... deadlocks by analyzing the unsafe states. True, True, False False, True, True True, False, True False, True, False

State true or false.Deadlock detection is possible using the allocation and request matrices alone.A way to recover from deadlock is to take away the resource from one of...

roopkathaaa

831 views

roopkathaaa asked Sep 2, 2023

0 votes

1 answer

20

Design DFA contain all strings of a's and B's which each string starts with 'ab' and end with 'ab'.

BINDU Prasad

327 views

BINDU Prasad asked Jul 4, 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