UU-COM-3001 Computational theory 1
UU-COM-3001 Computational
theory
Assignment 3
Dear students,
This is your third and final assignment for this course that accounts for 60% of your
total marks for the course.
Problem 1
Consider the following languages over Σ = 0,1.
• L1 is the language described by (0+1)∗.
• L2 is the language of all strings that do not contain the pattern 00.
• L3 is the language of the DFA given by the following transition table:

• L4 is the language described by ε +0+1+(ε +0+1) (ε +0+1) ∗ (ε +0+1).
• L5 is the language of all strings that have at most two 0s.
• L6 is the language of the NFA given by the following transition table:

• L7 is the language described by 1∗(011∗)∗ +1∗(011∗)∗0.
Which of these languages are the same and which are different? To show two languages
are the same give a short proof, and to show two languages are different give a string
that is in one but not by the other. (You must provide an explanation to get credit.)
UU-COM-3001 Computational theory 2
Problem 2
This problem concerns languages over the alphabet Σ = 1. For any two integers q,r
≥0, define the language Lr,q over Σ as
Lr,q =1mq+r : m ≥0=1q,1q+r,12q+r,….
For instance, L1,3 =1,1111,1111111,….
(a) Show that for every q and r, the language Lr,q is regular.
(b) Show that if L is a regular language over Σ, then L can be written as
L = Lr1,q ∪ Lr2,q ∪···∪ Lrk,q ∪ L0,
where 0 ≤ r1 < ··· < rk are integers and L0 is a finite set.
Problem 3:
Suppose the following PDA P = (q, r, 0,1, Z0, X, δ, q, Z0, ∅) is given:

Start ϵ, X /ϵ
Convert P to a PDA P′ with L(P′) = N(P).
Problem 4:
Convert the grammar
S → 0S1 | A
A → 1A0 | S | ϵ
to a PDA that accepts the same language by empty stack.
Problem 5:
Consider the following grammar:
S → ASB | ϵ
A → aAS | a
B → SbS | A | bb
a. Eliminate all ϵ-productions.
b. Eliminate all unit productions from the resulting grammar in a).
c. Eliminate all useless symbols from the resulting grammar in b).
d. Put the resulting grammar in c) in Chomsky Normal Form.
q r
UU-COM-3001 Computational theory 3
Problem 6:
Context-free grammars are sometimes used to model natural languages. In this problem
you will model a fragment of the English language using context-free grammars.
Consider the following English sentences:
The girl is pretty.
The girl that the boy likes is pretty.
The girl that the boy that the clerk pushed likes is pretty.
The girl that the boy that the clerk that the girl knows pushed likes is pretty.
This is a special type of sentence built from a subject (The girl), a relative pronoun
(that) followed by another sentence, a verb (is) and an adjective (pretty).
(a) Give a context-free grammar G that models this special type of sentence. Your
terminals should be words or sequences of words like pretty or the girl.
(b) Is the language of G regular? If so, write a regular expression for it. If not, prove
using the pumping lemma for regular languages.
(c) Can you give an example of a sentence that is in G but does not make sense in
common English?
Your work needs to be well written and have quality information. Your work must be
clear and has to be able to educate someone with no prior knowledge in Compiler
design.
Assignment Evaluation Rules:
• Overall presentation 30%
• Solution correctness 50%
• Conclusion – What you have learned 20%
Notes:
• Please read and apply the rules for referencing.
• The assignment is your own individual work. I expect all sent assignments to
be very different from one another even if they are based on the same topic.
• The deadline is the end of week 4. Late assignments will NOT be accepted
unless for exceptional reasons.
• This is worth 60% of your mark