CS 4384 — Automata Theory, Homework 1

Download PDF

Prove that

Proof. Proof by induction:

Basis:

For ,

Inductive Hypothesis:

Assume for , .

Inductive Step:

Show that

By the inductive hypothesis

where the inequality holds for

Consider the DFA in the Exercise 1.3 on page 83 from the textbook. Draw the DFA and determine its result for each of the following inputs?

udududd

Not accepted (ends on q4)

01110

Accepted (ends on q3)

uuduuu

Not accepted (ends on q1)

Let be an alphabet. Design an FA that recognizes all the strings which start with aa and end with bb

Solve the Exercise 1.6 (parts (c), (i) and (k) only) on page 84 of the textbook

Construct a DFA for each part.

.c

.i

.k

Construct a NFA for each part.

.c

.i

.k

Design a DFA to accept the language

Let be an alphabet. Design a DFA for each language

The set of all of strings in which no two characters are the same

The same thing is redrawn (using a different format) for clarity.