Recent questions tagged minimal-state-automata

+2 votes

2 answers

1

UGCNET-June-2019-II-75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$

asked Jul 2, 2019 in Theory of Computation by Arjun Veteran (434k points) | 369 views

+15 votes

3 answers

2

GATE2019-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$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______

asked Feb 7, 2019 in Theory of Computation by Arjun Veteran (434k points) | 5.1k views

0 votes

1 answer

3

Self Doubt
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11.

asked Jan 19, 2019 in Theory of Computation by kumar.dilip Active (5.2k points) | 69 views

0 votes

0 answers

4

Testbook Test Series: Theory of Computation - Minimal State Automata
$Que-$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______. Approach ?

asked Jan 6, 2019 in Theory of Computation by Soumya29 Boss (16.4k points) | 101 views

0 votes

0 answers

5

[AppliedCourse Test] Min DFA of (a*b*) complement
The Minimum DFA that accepts the given language is ____ L = { w | w is any string not in a*b*}

asked Jan 5, 2019 in Theory of Computation by VikramRB (239 points) | 169 views

0 votes

1 answer

6

Self doubt TOC DFA
Construct a minimal DFA which accepts set of all strings over {a,b}, such that $1)$Second symbol from $RHS$ should be $‘a’$ $2)$Third symbol from $RHS$ should be $‘a’$

asked Dec 27, 2018 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 76 views

0 votes

2 answers

7

Minimal DFA
Given following NFA find the minimal equivalent DFA

asked Dec 14, 2018 in Theory of Computation by aditi19 Loyal (5.2k points) | 158 views

+3 votes

2 answers

8

ME test series DFA states
The number of states in minimal DFA for strings starting with $ab^{2}$ and ending with $b$ over the alphabet $\left \{ a,b \right \}$ is__________. // doubt: minimal string should be $ abb $ right?

asked Dec 13, 2018 in Theory of Computation by Devwritt Active (4.1k points) | 87 views

0 votes

1 answer

9

Reversal of DFA doubt
in reversal of DFA if there are more than one final states then which one will be made the initial state? a DFA can have only one initial state

asked Dec 10, 2018 in Theory of Computation by aditi19 Loyal (5.2k points) | 194 views

+2 votes

0 answers

10

Can't understand the intution behind the shortcut
let the ∑ = {0,1} ===> strings possible are should be Binary strings. No.of States in Minimal DFA that accepts, Decimal( Binary String ) = 0 mod n in ACE coaching institute, i learned that For Decimal( Binary String ) = 0 mod n i) if n ... String ) = 0 mod x or 0 mod y neither x divides y nor y divides x either x is divides y or y divides x

asked Nov 30, 2018 in Theory of Computation by Shaik Masthan Veteran (67.5k points) | 139 views

0 votes

1 answer

11

Finite Automata
When we convert a (minimal) NFA to DFA by subset construction method, is the DFA obtained always a minimal DFA? Please elaborate.

asked Nov 15, 2018 in Theory of Computation by Mizuki Active (1.4k points) | 97 views

+1 vote

1 answer

12

Doubt DFA
1.The minimum no of state in DFA that accept L={an| n is multiple of 3 but not 5} Ans 15 i did it and found that 3,5 relatively prime so 3*5=15 2.The minimum no of state in DFA that accept L={an| n is multiple of 2 but not 4} Ans 4 and done and found that 2,4 not relatively prime so max(2,4) =4 Can't a Conclude it??? Edited. thanks for rectification.

asked Nov 6, 2018 in Theory of Computation by Abhisek Tiwari 4 Loyal (5.3k points) | 306 views

+1 vote

1 answer

13

What is the minimal DFA for this language (11+111)*, for Σ={0,1}.
What is the number of states for the above DFA,please draw NFA,DFA and minimised DFA for the same.Also won't the language not accept epsilon?

asked Nov 6, 2018 in Theory of Computation by sripo Active (2.5k points) | 341 views

0 votes

0 answers

14

Finite Automata

asked Oct 18, 2018 in Theory of Computation by Sambhrant Maurya Active (4k points) | 89 views

0 votes

0 answers

15

Dfa for no states
What is the difference between a dfa accepting epsilon moves and dfa accepting nothing? I have a dfa which has no states what will be the dfa this is regarding,this question https://gateoverflow.in/8362/gate2015-1-52

asked Oct 17, 2018 in Theory of Computation by sripo Active (2.5k points) | 173 views

0 votes

0 answers

16

Construct DFA for given Language
For the language which ends with 01 or 11 or 10 or 11 for $\sum$={0,1}* .Is dfa possible for this language?

asked Oct 16, 2018 in Theory of Computation by sripo Active (2.5k points) | 55 views

+1 vote

1 answer

17

Grammar to DFA Construction
For the given Grammar S->aA|bB A->bC|aS B->aC|bS C->aB|bA Construct DFA I am getting confused in understanding how to take the final state.

asked Oct 13, 2018 in Theory of Computation by sripo Active (2.5k points) | 129 views

0 votes

0 answers

18

TOC : Minimum State in Finite Automata ( virtualgate )
For a binary string x = a0a1 · · · an−1 define val(x) to be the value of x interpreted as a binary number, where a0 is the most significant bit. More formally, val(x) is given by How many minimum states will be in a finite automaton that accepts exactly the set of binary strings x such that val(x) is divisible by either 4 or 5. Ans is 5 or 20?

asked Oct 12, 2018 in Theory of Computation by arya_stark Active (1.7k points) | 79 views

0 votes

1 answer

19

Number of States in TOC
Number of $2$ state DFA with designated initial state can be constructed over alphabet $\sum_{.}^{.}=\left \{ 0,1 \right \}$ and that accept empty language $\Phi$ is_______________

asked Oct 6, 2018 in Theory of Computation by srestha Veteran (119k points) | 162 views

0 votes

1 answer

20

Test Series
What will be the minimum no. of states for DFA for the above NFA? Please explain.

asked Sep 23, 2018 in Theory of Computation by Subham Nagar Active (1.1k points) | 50 views

0 votes

1 answer

21

Doubt in Automata
If two finite state machines M and N are isomorphic then M can be transformed to N by relabeling (a) the states alone (b) the edges alone (c) both the states and edges (d) none of the above

asked Sep 16, 2018 in Theory of Computation by goluabhinan (71 points) | 256 views

0 votes

1 answer

22

Doubt in Finite Automata
Consider the following DFA D. The number of states in the minimization of D is __________.

asked Sep 12, 2018 in Theory of Computation by goluabhinan (71 points) | 75 views

0 votes

1 answer

23

Minimal DFA
Minimum states required for DFA that accepts : L = {w1 x w2 | w,x belongs to {a,b}* | w1 >= 0, w2 > 1 and x >= 0 }.

asked Sep 10, 2018 in Theory of Computation by Na462 Loyal (7.1k points) | 52 views

+1 vote

0 answers

24

Minimum number of States
Ans. 5

asked Aug 30, 2018 in Theory of Computation by Na462 Loyal (7.1k points) | 95 views

0 votes

0 answers

25

minimum finite automata
construct the minimul FA, that accepts all the string of 0's and 1's A)The second symbol from the right end of the string is 0 B)The third symbol from the right end of the string is 1

asked Jul 10, 2018 in Theory of Computation by suraj patel (51 points) | 152 views

0 votes

1 answer

26

Minimum finite automata
Construct the Minimum FA that accepts all the string of 0's and 1's where A)Every String start and end with Zero. B)Every string Start and end with Same Symbol.

asked Jul 10, 2018 in Theory of Computation by suraj patel (51 points) | 170 views

0 votes

0 answers

27

Minimal dfa
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)

asked Jun 12, 2018 in Theory of Computation by Harshitha 123 (85 points) | 102 views

0 votes

1 answer

28

GATE CS Mock 2018 (Set -2)
Let δ denote the transition function and α denoted the extended transition function of the ε-NFA whose transition table is given below: Which of the following option is correct? A) α (q1,aba) is {q0, q2} B) null reachable states are {q0, q1, q2}B C) α (q3,bab) is {q0, q1, q2, q3} D) None of these

asked Jun 11, 2018 in Theory of Computation by Nikhil Patil Junior (505 points) | 155 views

0 votes

2 answers

29

Toc DFA

asked Jun 6, 2018 in Theory of Computation by Prince Sindhiya Loyal (5.9k points) | 95 views

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

Recent questions tagged minimal-state-automata

Recent Posts

Recent Blog Comments