Consider the Finite Automaton below.
a. Construct the smallest Deterministic Finite Automaton
which accepts the same language. Don't forget to include a
dead state if there is nowhere to go in the non-deterministic
machine from some state on some symbol.
b. Draw a regular expression that represents the language
accepted by your machine.
c. Write down a Regular (Linear) Grammar that generates
it.
You must prove that your choice is correct. Use the pumping
lemma, and/or closure arguments.
Recall that a decision algorithm is an algorithm that returns a
yes or no answer. Give decision algorithms to determine
if a Regular set
Recall that a right-linear grammar is one where every production is either in the from A->aB or A ->b, where a and b are terminal symbols. and A and B are non-terminal symbols. Every regular set can be generated by a right-linear grammar and every right-linear grammar generates a regular set. Thus, a right-linear grammar is equivalent to a finite state machine, and we call a right-linear grammar regular..
a. Write down a right-linear grammar to generate the set of strings that are evenly divisible by 5 when interpreted as a binary string.
b. A left-linear grammar is a context-free grammar where each production must be either in the form A->Ba, or A->b, where a and b are terminal symbols and A and B are non-terminals. Left-linear grammars are also equivalent to finite state machines. Explain how to convert a given finite state machine, to an equivalent left-linear grammar. You may use an example to illustrate.
5. Single Symbol Regular Languages (2 points)Hint: Let L be the language generated by some right-linear grammar G. Reversing the right sides of each production in G creates a left linear grammar that generates the reverse of L.
Describe a method to implement the FSM minimization algorithm that runs in O(n log n) time, rather than O(n2). Write a program implementing your method.