Scribd
Upload
32 views3 pages

DFA NFA Conversion Notes

The document explains the definitions and examples of Deterministic Finite Automaton (DFA) and Non-Deterministic Finite Automaton (NFA), highlighting their structures and transition functions. It also details the NFA to DFA conversion process using the subset construction method, providing a step-by-step example. The document concludes with a specific example of converting an NFA to a DFA, illustrating the states and transitions involved.

Uploaded by

bravish gujar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views3 pages

DFA NFA Conversion Notes

The document explains the definitions and examples of Deterministic Finite Automaton (DFA) and Non-Deterministic Finite Automaton (NFA), highlighting their structures and transition functions. It also details the NFA to DFA conversion process using the subset construction method, providing a step-by-step example. The document concludes with a specific example of converting an NFA to a DFA, illustrating the states and transitions involved.

Uploaded by

bravish gujar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DFA, NFA and NFA to DFA Conversion

1. DFA - Definition and Example

Definition:

A Deterministic Finite Automaton (DFA) is a machine that, for each state and input symbol, has exactly one

transition to another state.

Formal Definition:

A DFA is a 5-tuple (Q, S, delta, q, F), where:

- Q: Finite set of states

- S: Finite input alphabet

- delta: Transition function (Q S -> Q)

- q: Start state (q in Q)

- F: Set of accepting/final states (F subset of Q)

Example:

Design a DFA to accept all strings over {0,1} that end with '01'.

States: q0 (start), q1, q2 (accept)

Transitions:

- delta(q0, 0) = q1

- delta(q0, 1) = q0

- delta(q1, 0) = q1

- delta(q1, 1) = q2

- delta(q2, 0) = q1

- delta(q2, 1) = q0

Accepting State: q2

2. NFA - Definition and Example

Definition:

A Non-Deterministic Finite Automaton (NFA) allows multiple transitions for the same input or epsilon ()

transitions.
DFA, NFA and NFA to DFA Conversion

Formal Definition:

An NFA is a 5-tuple (Q, S, delta, q, F), where:

- delta: Q (S {}) -> 2^Q (transition to a set of states)

Example:

Accept strings that start with '1' over {0,1}.

States: q0 (start), q1 (accept)

Transitions:

- delta(q0, 1) = {q1}

- delta(q1, 0) = {q1}

- delta(q1, 1) = {q1}

Accepting State: q1

3. NFA to DFA Conversion - Explanation and Example

NFA to DFA Conversion (Subset Construction Method):

Steps:

1. Start State: -closure of the NFA's start state.

2. Each DFA state is a set of NFA states.

3. For each DFA state and input symbol:

- Determine all transitions from all NFA states in the set.

- Take -closure of the resulting set.

4. Mark any DFA state containing at least one NFA final state as accepting.

Example:

Given NFA:

- Q = {q0, q1}, S = {a}, F = {q1}

- delta(q0, a) = {q0, q1}

- delta(q1, a) =

Convert to DFA:
DFA, NFA and NFA to DFA Conversion

1. Start with state {q0}

2. delta({q0}, a) = {q0, q1}

3. delta({q0, q1}, a) = {q0, q1}

4. Accepting state: {q0, q1} (contains q1)

DFA:

- States: A = {q0}, B = {q0, q1}

- Transitions:

- delta(A, a) = B

- delta(B, a) = B

- Accepting State: B

You might also like