Question

Given an alphabet Σ = {a, b, c, d} Use Lecture definition to construct a nondeterministic automaton M such that L = {w ∈ Σ ∗ : at least one letter from Σ is missing in w}

1. (5pts) Draw the diagram Just draw the diagram, do not list the components

2. (2pts) Explain shortly why your M is nondeterministic and why it is correct

3. (3pts) Show that (s, accabb) `M ∗ (q, e) by constructing a computation of the word accabb in M, where s is the initial state of M and q is its certain final state

Answer 1

Solution

Part 1

Part 2

A finite automata is nondeterministic if there is 0 or more than one transitions corresponding to a symbol from any state.

Above finite automata is non deterministic because the start state q0 has 3 different transitions corresponding to symbol a, 3 different transitions corresponding to symbol b , 3 different transitions corresponding to symbol c and 3 different transitions coresponding to symbol d.

Part 3

(q0, accabb)

(q1,ccabb)

(q1,cabb)

(q1,abb)

(q1,bb)

(q1,b)

(q1,ϵ)