GATE CSE 2017 Set 1 | Question: 22

Question

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

Comments

Check https://gateoverflow.in/blog/8795/minimal-deterministic-finite-automata

---

@Asim Siddiqui 4 Make a NFA, convert it to DFA and then to minimal DFA.

 

---

Very Good Question

Answer 1

Minimum no. of states required if n^th symbol is fixed from right hand side is 2ⁿ

Here 2nd symbol from right hand side is fix

so answer will be 2² = 4

Answer 2

RE=(a+b)*b(a+b)

Here 2nd symbol from right is b  required 2^2 =4 state in Minimal DFA

(If  nth symbol from right is fixed then require k^n state in Minimal DFA where k is no. Of input alphabet in string)

Answer 3

the answer is following :-  a first we made a nfa using the given expression and then we converted it into dfa its simple.

Answer 4

By looking to expression  we can know 2 last  symbol is b and after a or b accepted .it is language which is 2 last symbol is b reading from rhs to LHS.
So here formula for this type of language 2^n
So here 2^2 =4