Search code examples
dfa

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

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.

Solution

  • 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, Σ, δ, q0, 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 (q0 ∈ 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.