Reference no: EM132780693

UU-COM-3001 Computational theory - Unicaf University

Assignment 1

Problem 1

Given a DFA for the following languages, specified by a transition diagram. For each one of them, give a short and clear description of how the machine works. Assume the alphabet is Σ = {0,1,2}:

(a) L1 = {w | w is any string over Σ that contains at least one '0'.}

(b) L2 = {w | w contains even number of 0s and an odd number of 1s.}

(c) L3 = {w = 0u12v | u,v are any strings over Σ.}

Problem 2

This problem concerns the NFA given by the following transition table:

	0	1
→ q0	{q0}	{q0, q1}
q1	Φ	{q1, q2}
∗q2	Φ	Φ

Convert this NFA to a DFA using the method described in class. Specify the DFA by its transition diagram.

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 Computational theory.

Assignment 2

Problem 1:

Construct a Turing machine that transforms an initial tape of the form 0m10n (m and n 0's with m, n > 0 separated by a 1) into 0m1_0n (m and n 0's with m, n > 0 separated by a 1 followed by a blank). The tape head should be at the 1 before and after the computation. Run your machine on the input 00100.

Problem 2:

Consider the language L = {w010w | w ∈ Ld}. Is this language recursively enumerable? Justify your answer.

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 Computational theory.

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.rar