联系方式

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

您当前位置:首页 >> Web程序Web程序

日期:2020-03-19 01:11

CS 181 FINAL EXAM
WINTER 2020
You have 3 hours to complete this exam. You may state without proof any fact
taught in class or assigned as homework. Your algorithms must terminate on all
inputs.
1 Construct one-tape, deterministic Turing machines that decide the languages below. You
must provide both a state-transition diagram and a detailed verbal description:
a. binary strings of the form (0n1)k
(3 pts) , where n ≥ 0 and k ≥ 0;
(3 pts) b. binary strings (including ε) that represent properly nested parentheses, where 0
denotes an open parenthesis and 1 denotes a close parenthesis.
(3 pts) 2 Give an algorithm that takes as input a DFA D and determines whether D accepts at
least two palindromes.
(3 pts) 3 A language L is called downward-closed if for every string w that L contains, L also
contains every prefix of w. Give an algorithm that takes as input a regular expression R
and decides whether the language that R generates is downward-closed.
(3 pts) 4 A variable T in a context-free grammar G is called essential if every derivation of every
string by G uses the variable T. Give an algorithm that takes as input a context-free
grammar G and a variable T, and decides whether T is essential in G.
(3 pts) 5 A string w is said to cover a given PDA P if there is a computation by P on w such
that every state of P is visited. Give an algorithm that takes as input a PDA P and
decides whether there is a string that covers P.
(2 pts) 6 Prove that every infinite decidable language can be partitioned into two disjoint infinite
decidable languages.
7 For each problem below, determine whether it is decidable and prove your answer:
(2.5 pts) a. on input a Turing machine M and a symbol σ, decide whether M ever writes σ on
the tape in any computation;
(2.5 pts) b. on input a Turing machine M, decide if M recognizes a decidable language.

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