Question

- Give 3 examples for NFA. - Define the Machine Definition for each. - Design the Graph representation - Design Table Representation - Define the Language they accept

Answer 1

Sure! Here are three examples of NFAs, along with their machine definitions, graph representations, table representations, and the languages they accept:

### Example 1

#### NFA Machine Definition

- Q = {q0, q1, q2}

- Σ = {0, 1}

- δ = a transition function that maps (Q x Σ) to P(Q)

- δ(q0, 0) = {q0, q1}

- δ(q0, 1) = {q0}

- δ(q1, 1) = {q2}

- δ(q2, 0) = {q2}

- δ(q2, 1) = {q2}

- q0 = the start state

- F = {q2} (the accept state)

#### Graph Representation

```

->(q0)--0-->(q0, q1)

| |

1 1

| |

v v

(q0) (q2)

| |

0 1

| |

v v

(q2)<--1--(q2)

```

#### Table Representation

| | 0 | 1 |

|---|-------------|-------------|

| q0| {q0, q1} | {q0} |

| q1| Ø | {q2} |

| q2| {q2} | {q2} |

#### Language Accepted

This NFA accepts the language of all strings that end in the substring "11". For example, "011", "111", "00111", "0010011", etc.

### Example 2

#### NFA Machine Definition

- Q = {q0, q1, q2}

- Σ = {0, 1}

- δ = a transition function that maps (Q x Σ) to P(Q)

- δ(q0, 0) = {q0}

- δ(q0, 1) = {q0, q1}

- δ(q1, 0) = {q2}

- δ(q1, 1) = {q2}

- δ(q2, 0) = {q2}

- δ(q2, 1) = {q2}

- q0 = the