1. The following Questions are based on DFA Part 4 Slides

(a) Find the minimal strings for the following string expressions

ab*|c*

ab*|c⁺

(a|b)*

(a(c|d)*e³b)*

(a(c|d)*e³b)

(b) Find the subgroup of strings for the following string expressions

ab*|c*

ab*|c⁺

(a|b)*

(a(c|d)*e³b)*

(a(c|d)*e³b)

(c) Find the subgroup of strings that are under * for the following string expressions

ab*|c*

ab*|c⁺

(a|b)*

(a(c|d)*e³b)*

(a(c|d)*e³b)

(d) Based on the formula we learned, for the following string expression, determine

how many states are required to accept the minimal string by a DFA ?

(a(cb|d)*e³b)

how many additional states are required to accept the subgroup of strings under * ?

Draw the DFA that accepts the given string .

2.

Explain, in your own language, that 1ⁿ0ⁿ, for n>1 is not accepted by a DFA using the following two methods:

Showing that the expression contradicts with pumping lemma requirements

Showing that the expression will require a DFA with an infinite number of states to be accepted

3.

Compute AUB, A* and AB for the following A and B

A={ab*|c} and B={d}

Draw three DFAs to accept AUB, A* and AB for the following A and B.

A={ab*|c} and B={d}

What languages the following two grammars individually generate ?

Grammar 1

A a

A aB

B c

B d

Grammar 2

A aC

A aB

B cB

B

C

Build grammars for each of the following regular languages :

Language 1: a*bc

Language 2: a⁺bc*