CS 4384 — Automata Theory, Homework 1
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.