COT 4810 Homework #1 (9/9-9/11), Due 9/18 in Class

COT 4810 Homework #1 (9/9-9/11), due 9/18 in class

Finite Automata (Cht. 2)

1) Construct a DFA M over the alphabet {a,b} that accepts all strings that contain the substring bb.

There are many solutions. Here's one:

Q = {q1, q2, q3}

Start State = q1

Accept States = {q3}



Input State / Character / Output State
q1 / a / q1
q1 / b / q2
q2 / a / q1
q2 / b / q3
q3 / a / q3
q3 / b / q3

2) Construct a DFA M over the alphabet {a,b} that accepts all strings that do not contain the substring aa.

There are many solutions. Here's one:

Q = {q1, q2, q3}

Start State = q1

Accept States = {q1, q2}



Input State / Character / Output State
q1 / a / q2
q1 / b / q1
q2 / a / q3
q2 / b / q1
q3 / a / q3
q3 / b / q3

Regular Expressions (Cht. 14)

3) Find a regular expression that describes the language accepted by the DFA specified below:

Q = {A, B, C}

 = {0, 1}

start state = A

accepting states = B, C

 =

State\Input / 0 / 1
A / A / B
B / C / A
C / B / C

Since there are two accept states, we'll get the regular expression from two separate automata. First, consider the same automata above, with the accept state being B.

In this automata, we must remove state C. When we do this, we find that we add the following transition on a regular expression:

B  B: 01*0

Our final regular expression would then be: 0*1((01*0)*10*1)*

Now, consider the same automata with just C as an accept state. Here we must remove state B. In doing this we'll add two transitionson a regular expression:

A  C: 10

C  A: 01

Our final regular expression would then be: 0*10(1*010*10)*

We must union these two to get:

0*1((01*0)*10*1)*  0*10(1*010*10)*

Nondeterminism (Cht. 26)

4) Construct an NFA over the alphabet {a,b} that accepts any string that ends with 4 consecutive a's.

Sorry, you can do this question easily with a DFA as well. My intention was for the question to read, "Construct an NFA over the alphabet {a,b} that acceps any string that ends with the string abab."

Here is the DFA:

Q = {q1, q2, q3, q4, q5}

Start State = q1

Accept States = {q5}



Input State / Character / Output State
q1 / a / q2
q1 / b / q1
q2 / a / q3
q2 / b / q1
q3 / a / q4
q3 / b / q1
q4 / a / q5
q4 / b / q1
q5 / a / q5
q5 / b / q1

Generative Grammars (Cht. 23)

5) Make five sentences from Steve's language:

S  NP+VP

VP  Verb+Adj

NP  Det + N

Verb  is | see | listened | spoke | ate | drank | clicked | sat

Det  this | a | the | my | his

Adj  great | hot | cool | sweet | well | smoothly

N  topic | coffee | computer | desk | clock

Many solutions here as well. Here are five sentences:

This topic is great. A computer spoke well. The coffee is hot. My clock clicked smoothly. His desk ate great.

6) What kind of grammar is Steve's grammar? (Note: This is a bit more tricky question than it looks.)

The grammar is finite and therefore is a Type-3 grammar.

The Chomsky Hierarchy (Cht. 7)

7) Construct a type-3 grammar for the language denoted by the regular expression (ab)*c(ba)*.

Here is one answer:

S  cC | aB

B  bS

C  | bD

D  aC