CS662设计程序辅导、讲解Java，c/c++编程、Python程序辅导辅导R语言程序|讲解数据库SQL

项目预算：开发周期：发布时间：要求地区：

PRACTICE FINAL EXAM CS662
SOLUTION: Think in terms of a 4-tape Turing machine: first put all the a’s onto one tape, then all the
b’s onto the second tape, then all the c’s onto the third tape. Then just loop through all 3 tapes at
once. Reject if there is an a without a b, or a b without a c. Otherwise once we’re at the end of the
tape, accept.
3) Design a TM for strings that have the same number of a’s and b’s: Give an outline first.
SOLUTIONS:
A computation of the machine begins by finding the first a on the tape and replacing it with an X (state q1). The
tape head is then returned to position zero and a search is initiated for a corresponding b. If a b is
encountered in state q3, an X is written and the tape head is repositioned to repeat the cycle q2, q3, q4, q5. If no
matching b is found, the computation halts in state q3 rejecting the input. After all the a’s have been
processed, the entire string 4 is read in q5 and q6 is entered upon reading the trailing blank. The computation
halts in the accepting state qf if no b’s remain on the tape.
Transitions (in a tabular form, easier to read)
4) If L is a recursively enumerable (RE) language, then the strings in L can be accepted by a:
____________________.
5) If L is a recursively enumerable (RE) language, then the strings in L can be generated by an
_______________ grammar.
6) If L is RE but not recursive, then its complement cannot be RE (true or false). ____________
7) Give context-free grammars that generate the following languages.
8) Transform the grammar with productions S → abAB A → baB|λ B → BAa|A|λ into
Chomsky normal form.
Solutions:
Removing λ−productions: Here A and B are nullable variables. Then following the second step of
construction in Theorem 6.3 in the textbook, we get:
S → abAB|abA|abB|ab A → baB|ba B → BAa|A|Ba|Aa|a
Removing unit-productions(by Theorem 6.4):
S → abAB|abA|abB|ab A → baB|ba B → BAa|baB|ba|Ba|Aa|a.
There are no useless productions in the grammar. By step 1 of Theorem 6.6, 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
By step 2 of Theorem 6.6, 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
9) Convert the following grammar into Greibach form, then construct a corresponding NPDA:
S → aABB|aAA A → aBB|a B → bBB|A.
Solutions:
The grammar does not have any λ−productions. So we can convert it into Greibach normal form. By
applying Theorem 6.1 on last production,
S → aABB|aAA A → aBB|a B → bBB|aBB|a
By applying construction in Theorem 7.1, 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)}
10) Eliminate useless productions from
S → a|aA|B|C A → aB|λ B → Aa C → cCD D → ddd.
Solutions:
Remove those variables that do not produce any strings then remove the unreachable variables.
S → a|aA|B A → aB|λ B → Aa,
11) Construct an NPDA that accepts the following language on Σ = {a, b}, L = {w | na(w) = nb(w) + 1}.
Solutions:
M = ({q0, q1, q2}, Σ, {a, b, z}, δ, q0, z, {q2}) with
δ(q0, λ, z) = {(q1, az)} δ(q1, a, z) = {(q1, az)} δ(q1, a, a) = {(q1, aa)}
δ(q1, a, b) = {(q1, λ)} δ(q1, b, z) = {(q1, bz)} δ(q1, b, a) = {(q1, λ)}
δ(q1, b, b) = {(q1, bb)} δ(q1, λ, z) = {(q2, λ)} δ(q1, c, z) = {(q1, c)}
δ(q1, c, a) = {(qa, a)} δ(q1, c, b) = {(q1, b)}
Then M accepts L since it starts with one extra a on the stack and then uses the machine given in Example 7.4
to tell if the number of as and bs are the same. If they are and we started with one more a on the stack, then
the condition of L is met.
12) Set of all strings that are at least of length 4 and contains even number of 1’s.
Solutions:

CS662设计程序辅导、讲解Java，c/c++编程、Python程序辅导 辅导R语言程序|讲解数据库SQL

CS662设计程序辅导、讲解Java，c/c++编程、Python程序辅导辅导R语言程序|讲解数据库SQL