Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Comp 330: Mid-term examination

Regular Languages

1. Let M be the language defined by the regular expression (aaa)* − (aa)*.

(a) (10 points) Build a deterministic finite automaton (DFA) accepting M (Hint: Start by building a DFA accepting the regular language K = (aaa)* and another DFA accepting the regular language K = (aa)*. Then, note that M = K − L = K ∩ L¯).

(b) (5 points) Is the language M empty? Is it finite? Justify your answers.

(c) (5 points) Using your automaton, find a (simple) regular expression for M.

2. (10 points) Using the pumping lemma for regular languages, show that the language L of words that are not palindromes (i.e., a palindrome is a string that reads the same forward and backward) is not a regular language (Hint: use the pumping lemma to show that the complement of L is not regular).

Context-Free Languages

3. Let T be the language such T = {a i b j | i ≠ j}

(a) (10 points) Show that T is a context-free language (CFL) by proposing a context-free grammar (CFG) that generates its (Hint: Start with CFGs generating the CFL’s U = {a i b j | i < j} and V = {a i b j | i > j}).

(b) (10 points) Find a PDA accepting T.

(c) (10 points) What is the language a*b* − T?

(d) (10 points) Show that T is not regular (Hint: assume the opposite and use the argument above).

4. Let G be a context-free grammar (CFG):

S → SP | aP b | aQ

P → aP b | Q | ϵ

Q → aQ

R → RQ | b

(a) (10 points) Simplify the grammar (i.e., eliminate ϵ productions, unit productions and useless symbols, all in the correct order). Then, write the grammar under its Chomsky Normal Form (CNF). Show your work and justify each steps.

(b) (10 points) Use the Cocke-Younger-Kasami (CYK) algorithm to decide if the string s = abaabb is a word of the language L(G).

(c) (10 points) Draw a derivation tree for s computed from your execution of the CYK algorithm. Highlight the symbols used in the CYK table.

(d) (5 points (bonus)) Describe the language L(G).