代写program留学生程序、代做Java程序设计、c++，Python编程语言调试

日期：2020-12-15 10:04

Problem 1:

Show that the language L = {w ∈ {a, b, c}?

: na(w) + nb(w) = nc(w)} is context-free, but not linear.

In order to show that the language is context-free, we will give the corresponding NPDA.

Define M = ({q0, q1}, Σ, {a, c, z}, δ, q0, z, {q1}) with

δ(q0, a, z) = {(q0, az)}, δ(q0, a, a) = {(q0, aa)}, δ(q0, a, c) = {(q0, λ)},

δ(q0, b, z) = {(q0, az)}, δ(q0, b, a) = {(q0, aa)}, δ(q0, b, c) = {(q0, λ)},

δ(q0, c, z) = {(q0, cz)}, δ(q0, c, a) = {(q0, λ)}, δ(q0, c, c) = {(q0, cc)},

δ(q0, λ, z) = {(q1, λ)}.

Then M accepts L since it keeps count of how many a’s and b’s are read with the stack symbol a and how many c’s

with the symbol c. For each a and b seen it will cancel a c if that is on the top of the stack or add an a. Similarly, for

each c seen, it will add a c to the stack or cancel an a if it is on top of the stack. Finally, we only accept if the number

of c’s is the same as the number of a’s and b’s combined, that is they all cancel each other on the stack.

To show that the language is not linear, we will use the pumping lemma for linear language. Assume that the

language is linear and apply the PL to the string w = amc

2mb

m.

|uvyz| ≤ m shows that in this case the strings u, v must both consist entirely of a’s, that is v = ak1 and y, z must both

consist entirely of b’s, that is y = bk2. If we pump this string once, we get am+k1

c

2mb

m+k2

, with either k1 ≥ 1 or k2 ≥ 1, a

result that is not in L. This is a contradiction, it proves that the language is not linear.

Problem 2:

Show that the family of context-free languages is not closed under difference in general, but is closed under regular

difference, that is, if L1 is context-free and L2 is regular, then L1 ? L2 is context-free.

To show that context free languages are not closed under difference in general, we will give two context free

languages whose difference is no longer context free. Let L1 = {an b

n

c

m |m, n ≥ 0} and L2 = {??????

???? ????????????? | m, n ≥ 0}. L1

and L2 are both context free languages (in fact deterministic context free languages),

which is not context free as stated in class. Thus, the family of context free languages is not closed under

difference.

Next, we will show that the class of context free languages is closed under regular difference. Let L1 be any context

free language and L2 be any regular language. We know that regular languages are closed under complement,

therefore L2 is a regular language. We also know that context free languages are closed under regular intersection.

Thus, L = L1 ? L2 = L1 ∩ ??2

??? is a result of a regular intersection and is therefore a context free language.

Problem 3:

Design Turing machines to compute the function for x and y positive integers represented in unary. For each of

these problems let u(x) = 1x where 1x

is 1 concatenated with itself x times.

We will assume that u(0) = λ and will be represented by the tape having only blanks on it.

(a) ??(??) = 3 ??.

The input to our tape will be u(x) and the output will be u(3x). We will first mark all the 1’s and then for

every marked 1 we see we will write two 1’s at the end of the string, thus tripling the string. We will define

the TM as follows:

States Q = {q0, q1, q2, q3, qf}, where q0 is the start state and qf the only final state,

The input to our tape will be u(x) ? u(y) and the output will be u(x ? y) if x > y and the blank tape otherwise.

One strategy will be to remove a 1 from the end of the string (the y portion) and then remove a

corresponding 1 from the front of the string (the x portion). We continue until either we are out of 1’s in

the y portion, in which case we have u(x ? y) on the tape, or we are out of 1’s in the x portion in which case

x ≤ y, so we clear the tape and halt with the blank tape.

c) ??(??, ??) = 2?? + 3??

The input to the tape will be u(x) + u(y) and the output will be u(2x + 3y). We will first mark all the 1’s

before the plus with one dot and then change the plus to a one with two dots and continue marking every

one after it with two dots. We will remove the last 1 as extra to the sum. Then for every 1 with two dots

seen we will write two 1’s and the end of the string and for every 1 with one dot we will write one 1 and

the end of the string, yielding the required total.

The input to the tape will be u(x) and the output will be u( ???2? ). Our strategy is to mark a 1 at the start of

the string and remove a corresponding one at the end of the string. We will repeat marking the next

unmarked 1 at the beginning and removing another 1 at the end. We will continue until there is no

unmarked 1 left (x was even) and we cut the output in half, or there is no one left to remove at the end (x

was odd) and the output is the fraction rounded up. Then we clear all marks and halt.

e) ??(??) = ?? ?????? 5

The input to the tape will be u(x) and the output will be u(x mod 5). Our strategy is to mark all the 1’s as we

scan to the right using our states to remember how many 1’s we have seen mod 5. Then we will remove

the marks from that many 1’s and scan back to the left over the remaining marked 1’s. Then we will delete

all the marked ones and halt with x mod 5 on the tape.

Problem 4:

Let L be a deterministic context-free language and define a new language L1 = {w| aw ∈ L, a ∈ Σ}. Is it necessarily

true that L1 is a deterministic context free language?

No! Let’s give a counter-example. Let L = {c an b

n

| n ≥ 0} ∪ {d an b 2n | n ≥ 0}, then L is a deterministic context free

language, if we start with a c we follow a branch where we accept or if we read an a we push one extra a on the

stack and then pop one a for each b read, accepting only if the stack is empty. If we start with a d, then we follow

another branch where we accept or if we read an a we push two extra a’s on the stack and then for each b rea d we

pop one a, accepting only if the stack is empty. In every configuration we can only move to one other configuration,

meeting the criteria for determinism. However, then L1 = {an b

n

| n ≥ 0} ∪ {a

n b

2n | n ≥ 0} (removing the first symbol

from every string in L), which is the language in Example 7.11 (Peter Liz 3rd ed.) which was shown in the example to

be nondeterministic.

Problem 5:

Transform the grammar with productions S → abAB, A → baB|λ, B → BAa|A|λ. into Chomsky normal form.

Removing λ?productions:

Here A and B are nullable variables, we get

S → abAB|abA|abB|ab, A → baB|ba, B → BAa|A|Ba|Aa|a.

Removing unit-productions:

S → abAB|abA|abB|ab, A → baB|ba, B → BAa|baB|ba|Ba|Aa|a.

There are no useless productions in the grammar.

Now, we introduce variables C and D to substitute terminals a and b.

S → CDAB|CDA|CDB|CD, A → DCB|DC,

B → BAC|DCB|DC|BC|AC|a, C → a, D → b.

Finally, we introduce variables to shorten the right sides of the production.

S → EF|EA|EB|CD A → GB|DC, B → BH|GB|DC|BC|AC|a,

E → CD, F → AB, G → DC, H → AC, C → a, D → b.

Problem 6:

Construct an NPDA corresponding to the grammar S → aABB|aAA, A → aBB|a, B → bBB|A.

The grammar does not have any λ?productions. So, we can convert it into Greibach normal form. Get rid of the unit

production,

S → aABB|aAA, A → aBB|a, B → bBB|aBB|a.

Define M = ({q0, q1, qf }, Σ, {S, A, B, z}, δ, q0, z, {qf }) with

δ(q0, λ, z) = {(q1, Sz)}, δ(q1, a, S) = {(q1, ABB),(q1, AA)},

δ(q1, a, A) = {(q1, BB),(q1, λ)}, δ(q1, b, B) = {(q1, BB)},

δ(q1, a, B) = {(q1, BB),(q1, λ)}, δ(q1, λ, z) = {(qf , z)}

Problem 7:

Is it possible for a regular grammar to be ambiguous?

Yes. Consider the grammar

S → A|λ A → λ.

Then there are two leftmost derivations that generate the string λ. The first is S ? λ and the second is S ? A ? λ.

Thus, this regular grammar is ambiguous. Regular grammars cannot be inherently ambiguous.

Problem 8:

Eliminate useless productions from S → a|aA|B|C, A → aB|λ, B → Aa, C → cCD, D → ddd.

Following the algorithm given in the proof of Theorem 6.2 (3rd edition), we will first remove productions that

cannot generate any strings. Let V1 = ?. Since S → a, A → λ and D → ddd are productions we add S, A and D to V1.

Then, since B → Aa is a production we add B to V1. There are no more variables that can produce a string following

the algorithm. Removing these useless productions yields the grammar

S → a|aA|B, A → aB|λ, B → Aa, D → ddd.

Next, we remove the unreachable variables. We will start with V2 = {S} since S is the start variable, we always reach

it. We can reach the variables A and B from S so they are added to V2. A and B can only reach each other so our

algorithm terminates. Since D is not in V2 it cannot be reached by any derivation of this grammar. Therefore, we

remove all productions with D, yielding the final grammar free of useless productions and useless variables.

S → a|aA|B, A → aB|λ, B → Aa,

Problem 8:

Construct NPDA that accept the following language on Σ = {a, b, c}. (a) L = {an b

2n | n ≥ 0}.

Define M = ({q0, q1, q2, q3}, Σ, {a, z}, δ, q0, z, {q0, q3})

with δ(q0, a, z) = {(q1, aaz)}, δ(q1, a, a) = {(q1, aaa)},

δ(q1, b, a) = {(q2, λ)}, δ(q2, b, a) = {(q2, λ)}, δ(q2, λ, z) = {(q3, λ)}.

Then M accepts L since it accepts the empty string and for each a seen it pushes two additional a’s onto the stack (3

total). Then it pops one a for each b seen guaranteeing there are twice as many b’s as a’s. Finally, it accepts if the

input is done and there are no more a’s on the stack.