AUTOMATA, LANGUAGES AND COMPUTATION

Automata, Languages and Computation

[Name of Student]

Automata, Languages and Computation

Question 1

A gambler starts with £10 and plays a game in which he repeatedly tosses a coin. If it turns up heads he wins £1 and, if it turns up tails, he loses £1. If we represent “heads” by H and “tails” by T, and let S = {H,T}, then every sequence of coin tosses is represented by an element of S*. The gambler wins if he reaches £20 and loses if he reaches £0. Given these rules, some sequence is winning, such as:

S = HTTHHHHTHHHTHHHTHHHH

S = HTHHHHTHHHTHHHTHHHHT

S = HHHHHTHHHTHHHTHHHHTT

S = HTTHHHHTHHHTHHHTHHHH

S = HHHHHHHHTHHHTHHHHTTT

S = HHHHHHHHHHHHHHHTTTTT

S = HTHHHHHHHHHHHHHHTTTT

S = HHTHHHHHHHHHHHHHTTTT

S = HHHTHHHHHHHHHHHHTTTT

S = HHHHTHHHHHHHHHHHTTTT

S = HHHHHTHHHHHHHHHHTTTT

S = HHHHHHTHHHHHHHHHTTTT

S = HHHHHHHTHHHHHHHHTTTT

S = HHHHHHHHTHHHHHHHTTTT

S = HHHHHHHHHTHHHHHHTTTT

S = HHHHHHHHHHTHHHHHTTTT

S = HHHHHHHHHHHTHHHHTTTT

S = HHHHHHHHHHHHTHHHTTTT

S = HHHHHHHHHHHHHTHHTTTT

S = HHHHHHHHHHHHHHTHTTTT

S = HHHHHHHHHHHHHHHTTTTT

S = HTTHHHHHHHHHHHHHHTTT

S = HHTTHHHHHHHHHHHHHTTT

S = HHHTTHHHHHHHHHHHHTTT

S = HHHHTTHHHHHHHHHHHTTT

S = HHHHHTTHHHHHHHHHHTTT

S = HHHHHHTTHHHHHHHHHTTT

S = HHHHHHHTTHHHHHHHHTTT

S = HHHHHHHHTTHHHHHHHTTT

S = HHHHHHHHHTTHHHHHHTTT

S = HHHHHHHHHHTTHHHHHTTT

S = HHHHHHHHHHHTTHHHHTTT

S = HHHHHHHHHHHHTTHHHTTT

S = HHHHHHHHHHHHHTTHHTTT

S = HHHHHHHHHHHHHHTTHTTT

S = HTTTHHHHHHHHHHHHHHTT

S = HHTTTHHHHHHHHHHHHHTT

S = HHHTTTHHHHHHHHHHHHTT

S = HHHHTTTHHHHHHHHHHHTT

S = HHHHHTTTHHHHHHHHHHTT

S = HHHHHHTTTHHHHHHHHHTT

S = HHHHHHHTTTHHHHHHHHTT

S = HHHHHHHHTTTHHHHHHHTT

S = HHHHHHHHHTTTHHHHHHTT

S = HHHHHHHHHHTTTHHHHHTT

S = HHHHHHHHHHHTTTHHHHTT

S = HHHHHHHHHHHHTTTHHHTT

S = HHHHHHHHHHHHHTTTHHTT

S = HHHHHHHHHHHHHHTTTHTT

S = HTTTTHHHHHHHHHHHHHHT

S = HHTTTTHHHHHHHHHHHHHT

S = HHHTTTTHHHHHHHHHHHHT

S = HHHHTTTTHHHHHHHHHHHT

S = HHHHHTTTTHHHHHHHHHHT

S = HHHHHHTTTTHHHHHHHHHT

S = HHHHHHHTTTTHHHHHHHHT

S = HHHHHHHHTTTTHHHHHHHT

S = HHHHHHHHHTTTTHHHHHHT

S = HHHHHHHHHHTTTTHHHHHT

S = HHHHHHHHHHHTTTTHHHHT

S = HHHHHHHHHHHHTTTTHHHT

S = HHHHHHHHHHHHHTTTTHHT

S = HHHHHHHHHHHHHHTTTTHT

S = HTHHHHTHHHTHHHTHHHHT

S = HHHTHHHHHHHHHHHHTTTT

S = HHHHHHHHHTHHHHHHTTTT

S = HHHHHHHHHHHHHHHTTTTT

S = HHHHHHHHHHTTHHHHHTTT

S = HHHHHHHHHHHHHTTHHTTT

S = HHHHHTTTHHHHHHHHHHTT

S = HHHHHHHHHHHHHTTTHHTT

S = HHHHHHHHHHHTTTTHHHHT

S = HHHHHHHHTTTHHHHHHHTT

S = HHHHHHHHHTTTHHHHHHTT

S = HHHHHHHHHHTTTHHHHHTT

S = HHHHHHHHHHHTTTHHHHTT

S = HHHHHHHHHHHHTTTHHHTT

S = HHHHHHHHHHHHHTTTHHTT

S = HHHHHHHHHHHHHHTTTHTT

S = HTTTTHHHHHHHHHHHHHHT

S = HHTTTTHHHHHHHHHHHHHT

S = HHHTTTTHHHHHHHHHHHHT

S = HHHHTTTTHHHHHHHHHHHT

S = HHHHHTTTTHHHHHHHHHHT

Question 2

One of the results we demonstrated in the course was the following:

For every incomplete DFA, there exists an equivalent complete DFA. Consider the following assertion: For every complete DFA M = (Q,S,t, s,A), there exists an equivalent incomplete DFA N = (Q', S, t', s', A'). A finite automaton (AF) is a mathematical model computations performed automatically on an input to produce an output. Finite automata (AF) are of two types:

Deterministic (AFD)

Nondeterministic (AFDC)

In deterministic automation, each combination (state, input symbol) produces a single (state). Nonetheless, in nondeterministic automation, each combination (state, input symbol) produces several states (state1, State2……………………………….statei) where ? transitions are possible. A deterministic finite automaton can be represented by transition diagrams and transition tables. Transition diagrams represent:

nodes labeled by states (qi Q)

arcs between nodes qi to qj labeled with ei

(S i) if f (qi, ei) = qj

q0 is indicated by ?

F is indicated by qi * or double circle

Whereas, transition tables represent:

Rows led states (qi Q)

Columns headed by the input symbols (S i)

Example: Be the AFD1 = ({a, b}, {p, q, r}, f, p, {q}) where f is defined by:

f (p, a) = qf (p, b) = r

f (q, a) = qf (q, b) = r

f (r, a) = rf (r, b) = r

Configuration: is an ordered pair of the form (q, w) where:

Q: current status of AF

W: string is left to read at that moment, w S *

Initial configuration (q0, t)

Q0: initial state

T: input string ...