Recent questions tagged minimal-state-automata

Recent questions tagged minimal-state-automata

0 votes

0 answers

1

Minimal DFA
What will be the minimal DFA for $\left \{a^{n} :n mod 3 =0 \right \}\cup \left \{a^{n} :n mod 5 =1 \right \}$

ankit-saha asked in Theory of Computation Mar 24

93 views

0 votes

1 answer

2

DFA that accepts aaa or bbb as substring-: How to make?
https://i.stack.imgur.com/v70kK.jpg I have tried but it is wrong as it accepts abba. What is the correct dfa for this?

shivajikobardan asked in Theory of Computation Nov 1, 2021

by shivajikobardan

363 views

3 votes

1 answer

3

Number of final states
A FA accepting language L(A) has n states and m transition. ∑ = {a, b} L(A) is given as L(A)={ x | if x ∊ L(A) then u ∊ L(A) for $∃u, v ∊ ∑^{*}$ where x=uv } Find number of final state in above DFA?

Nishisahu asked in Theory of Computation Oct 8, 2021

181 views

4 votes

2 answers

4

UGC NET CSE | June 2019 | Part 2 | Question: 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$

Arjun asked in Theory of Computation Jul 2, 2019

by Arjun

3.0k views

35 votes

5 answers

5

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 _______

Arjun asked in Theory of Computation Feb 7, 2019

by Arjun

13.4k views

0 votes

1 answer

6

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.

kumar.dilip asked in Theory of Computation Jan 19, 2019

382 views

0 votes

0 answers

7

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 ?

Soumya29 asked in Theory of Computation Jan 6, 2019

334 views

0 votes

0 answers

8

[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*}

VikramRB asked in Theory of Computation Jan 5, 2019

1.8k views

0 votes

1 answer

9

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’$

Lakshman Patel RJIT asked in Theory of Computation Dec 27, 2018

by Lakshman Patel RJIT

276 views

0 votes

2 answers

10

Minimal DFA
Given following NFA find the minimal equivalent DFA

aditi19 asked in Theory of Computation Dec 14, 2018

766 views

3 votes

4 answers

11

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?

Devwritt asked in Theory of Computation Dec 13, 2018

615 views

2 votes

1 answer

12

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

aditi19 asked in Theory of Computation Dec 10, 2018

1.3k views

3 votes

0 answers

13

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

Shaik Masthan asked in Theory of Computation Nov 30, 2018

by Shaik Masthan

498 views

0 votes

1 answer

14

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

Mizuki asked in Theory of Computation Nov 15, 2018

by Mizuki

678 views

1 vote

1 answer

15

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.

Abhisek Tiwari 4 asked in Theory of Computation Nov 6, 2018

by Abhisek Tiwari 4

1.2k views

1 vote

1 answer

16

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?

sripo asked in Theory of Computation Nov 6, 2018

by sripo

1.9k views

0 votes

0 answers

17

Finite Automata

Sambhrant Maurya asked in Theory of Computation Oct 18, 2018

by Sambhrant Maurya

266 views

1 vote

0 answers

18

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

sripo asked in Theory of Computation Oct 17, 2018

by sripo

985 views

0 votes

0 answers

19

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?

sripo asked in Theory of Computation Oct 16, 2018

by sripo

213 views

1 vote

1 answer

20

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.

sripo asked in Theory of Computation Oct 13, 2018

by sripo

929 views

0 votes

0 answers

21

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?

arya_stark asked in Theory of Computation Oct 12, 2018

224 views

0 votes

1 answer

22

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_______________

srestha asked in Theory of Computation Oct 6, 2018

716 views

Page:

1
2
3
4
5
6
next »

Follow @gateoverflow

Recent questions tagged minimal-state-automata

Search GATE Overflow for GATE CSE