=========================preview======================
(COMP272)02qbank.pdf
Back to COMP272 Login to download
======================================================
COMP272 Question Bank #2
Pumping Theorem for Regular Languages Question 1
Are the following languages over alphabet = {a, b} regular? Prove your answers. a) {aiba2i : i 1}
b) {(bab)i(babbab)i : i 1}
c) {aibj : i<j , i, j 1}
d) {aibj : i>j , i, j 1}
Question 2
Using the pumping theorem, prove that the following languages are not regular:
.
a) {wwR : w {a, b}}
.
b) {ww : w {a, b}}
Minimum-state DFA Question 1
Find the minimum-state equivalent deterministic .nite automaton for each of the following .nite automata (deterministic in Figure 1 and nondeterministic in Figure 2).
Figure 1: DFA Figure 2: NFA
Uncountability, Finite representation Question 1
Problem 1.5.7 in Lewis and Papadimitriou (2nd. Edition).
Suppose we try to prove, by an argument exactly parallel to the proof of Theorem
1.5.2, that the set of all .nite subsets of N is uncountable. What goes wrong?
Question 2
Problem 1.5.8 in Lewis and Papadimitriou (2nd. Edition).
Give examples to show that the intersection of two countably in.nite sets can be
either .nite or countably in.nite, and that the intersection of two uncountable sets
can be .nite, countably in.nite, or uncountable.
Question 3
Let N ={0, 1, 2,..} be the set of whole numbers and Z = {.., -2,-1,0, 1, 2..} be
the set of all integers.
Give a bijection between N and Z.
Question 4
Show that ZZ is countable.
Question 5
Prove that:
a) The set of rational numbers, Q, is countably in.nite
p
(Hint: every rational number can be expressed as , where p Z, q N,
q
q .
= 0, and p, q are relatively prime)
b) (Q. 1.5.11 in textbook) The set of all real numbers in the interval [0, 1] is uncountable (Hint: refer to the hint in textbook)
Context-free Grammars Question 1
Show that the following languages are context-free by exhibiting context-free gram-mars generating each.
(a) {ambn : m n}
mbn
(b)
{acpdq : m + n = p + q}
(c)
{w {a, b}. : w has twice as many bs as as}
(d)
{w {a, b}. : w has equal number of as and bs}
(e) {w {a, b}. : w = wR}
Question 2
Let G =(V, , R, S), where V = {a, b, S}, = {a, b}, and R = {S aSb, S aSa, S bSa, S bSb, S e}. Show that L(G)= {w {a, b}. : w has even length}.
Question 3
Prove that all regular languages are context-free.
(Hint: Recall that in class we showed how to construct the context-free grammar corresponding to a particular DFA. You need to prove that the construction always works correctly.)
Question 4
Construct a pushdown automaton that accepts the language {aibj : i 2j}
Question 5
ibj
Construct a pushdown automaton that accepts the language {ack : i = j + k}
Pushdown Automata Question 1
.
Consider the alphabet = {a, b, (, ), ,, .}. Construct a context-free grammar which generates all strings in . that are regular expressions over {a, b}.
Question 2
Construct a pushdow