本次澳洲代写是一个计算机编译原理的assignment

Problem 1. (8 marks)

1. Consider the NFA over the alphabet fa, bg with initial state q1, final states
{q2, q5}, and transition relation:

(a) provide an equivalent DFA.
(b) provide a short English description of its language.

2. Consider the DFA over the alphabet fa, bg with initial state q1, final states
{q4, q5}, and transition function:

(a) provide an equivalent RE.
(b) provide a short English description of its language.

Problem 2. (6 marks) Consider the language L of strings u over alphabet fa, bg
such that the number of times b occurs in u is divisible by the number of times a
occurs in u. For example, bab, bba, bababb, bbbbbbbbaa, aaa are all in the language,
but aba, bbbaaaa, bb, babaaa are not. Prove that L is not regular using the fooling
argument. Format your proof as in lectures.

Problem 3. (6 marks) Provide an NFA that decides whether a given proposi
tional logic formula in CNF over three atoms is satisfiable.

The input formula will be given in the following format: Each clause is a string
over the alphabet x, y, z, X, Y, Z. Here x, y, z represent atoms and X, Y, Z repre
sent their negations. The clause is the disjunction of these literals. Clauses are
separated by #. The formula is the conjunction of the clauses.

For instance, the formula (x _ y) ^ (:z _ y) ^ 😡 is represented by the string
xy#Zy#X. Since the formula is satisfiable, the NFA should accept the string. On
the other hand the formula (:x _ y _ :z) ^ (:y _ :z) ^ z ^ x is represented by
the string XyZ#YZ#z#x. Since the formula is not satisfiable, the NFA should
reject this string.