Question

Automata Question.

Over the alphabet Σ = {a, b}:

1) Give a DFA, M₁, that accepts a Language L₁ = { w | w has exactly 2 a’s }

2) Give a DFA, M₂, that accepts a Language L₂ = { w | w has at least 2 b’s }

3) Give acceptor for L₁ intersection L₂

4) Give acceptor for L₁ - L₂

Answer 1

Deterministic Finite Automaton (DFA)

In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

Formal Definition of a DFA

A DFA can be represented by a 5-tuple (Q, ∑, δ, q₀, F) where −

1. A DFA, M₁, that accepts a Language L₁ = { w | w has exactly 2 a’s }

sol:

Here b's are free to choose.It means there can be any number of b's.

2.A DFA, M₂, that accepts a Language L₂ = { w | w has at least 2 b’s }

sol:

3.Acceptor for L₁ intersection L₂

4. Acceptor for L₁ - L₂

_{NOTE: Always remember for constructing DFA ,for problems like start,exactly,atmost it will require dead state and no dead state required for end,atleast,contain.}

• Q is a finite set of states.

• ∑ is a finite set of symbols called the alphabet.

• δ is the transition function where δ: Q × ∑ → Q

• q₀ is the initial state from where any input is processed (q₀ ∈ Q).

• F is a set of final state/states of Q (F ⊆ Q).

• Graphical Representation of a DFA

• A DFA is represented by digraphs called state diagram.

• The vertices represent the states.
• The arcs labeled with an input alphabet show the transition.
• The initial state is denoted by an empty single incoming arc.
• The final state is indicated by double circles.