Question

For all Questions below do the following. 1. 1pt Draw the State Diagram of M. 2. 2pt Determine whether M is / is not a finite state automata and determine whether M is deterministic or non-deterministic, if applicable. 3. 3pts Describe L(M) (1pt) and write a a regular expression (2pts) that defines it.

Q1 M = (K, Σ, s, ∆, F ) for K = {q0} = F, s = q0, Σ = ∅, ∆ = ∅.

Q2 M = (K, Σ, s, ∆, F ) for Σ = {a, b}, K = {q0, q1}, s = q0, F = {q1}, ∆ = {(q0, a, q1), (q1, a, q0)}.

Q3 M = (K, Σ, s, ∆, F ) for Σ = {a, b}, K = {q0, q1, q2, q3}, s = q0, F = ∅, ∆ = {(q0, a, q1), (q1, b, q2), (q2, a, q1), (q0, e, q3), (q2, a, q3)}.

Answer 1

All the three problems a finite state automata as its name suggests it should have a finite number of states and all the three have so.

1.

The initial as well as final state is q0 and since without any input and any transition the system reaches the final, state itself, its a NFA. (It needs some input for it to be a DFA)

L(M) = {}

2.

The automata defined here is a NFA and not a DFA as there is no transition defined for either q0 or q1 for input b.

L(M) = {a, aaa, aaaaa, aaaaaa....}

R = a(aa)*

3.

This automate also is a NFA but is a transducer as it has no final state so it keeps on taking input but with no final output.

L(M) = NULL