minimum no of states required for A(BC)*D?

Question

What are the minimum no. of states required in dfa of the language: A(BC)*D? Is it 3 or 4? By 3 I mean, can I write "BC" on single arrow? If possible please explain using a diagram. Thank you in advance.

Answer 1

The transition function of a DFA is typically defined as mapping a DFA state and one input symbol to another DFA state, take Wikipedia's formal definition as an example:

A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q₀, F), consisting of

• a finite set of states (Q)
• a finite set of input symbols called the alphabet (Σ)
• a transition function (δ : Q × Σ → Q)
• a start state (q₀ ∈ Q)
• a set of accept states (F ⊆ Q)

So with the usual definition of a DFA, you cannot have transitions over a sequence of two elements of the alphabet. A common kind of automaton that allows more complex transitions are Generalized nondeterministic finite automata.