Assignment 3 (Due 7 Apr at end of class)

General Rules:

a. Please hand in only your own work.
b. Grades discounted 10% per day late.

Tasks

1) Give a decision procedure (an algorithm) to determine if the set accepted by a DFA is cofinite (that is, its complement is finite).
2) Construct a CFG for {aⁱb^jc^k | either i != j or j != k}
3) Find, for the string bbaabaabbbaa and the grammar:
S-> aB | bA
A -> a | aS | bAA
B -> b | bS | aBB
a) left most derivation
b) right most derivation
c) parse tree
4) Construct a CFG for words which are subsets of {a,b,c}*, where each word has 3x as many a's and 2x as many b's as c's.
5) Find the CFG with no useless symbols equivalent to:
S -> CB | AC
B -> BA | CB
C -> a
A -> aB | b