Reference no: EM132780724
UU-COM-3001 Computational theory - Unicaf University
Assignment 3
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:
|
|
0
|
1
|
|
→∗q0
|
q1
|
q0
|
|
∗q1
|
q2
|
q1
|
|
∗q2
|
q3
|
q2
|
|
q3
|
q3
|
q3
|
• 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:
|
|
0
|
1
|
|
→∗q0
|
{q0, q1}
|
{q0}
|
|
∗q1
|
{q2}
|
Φ
|
|
∗q2
|
Φ
|
Φ
|
• 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.)
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:
0, Z0/XZ0 1, Z0/∈
0, X /XX 1, X /XX
1, X /X ∈, 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.
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.
Attachment:- Computational theory Assignment 3.rar