联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2020-12-18 10:57

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:


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp