计算理论 Theory of Computation

1. nLRA Problem (40 points) Recall the definition of a Lovesick Robot Automaton (LRA). A Lovesick Robot Automaton is a type of machine which takes a finite string as input, and generates an infinite pattern. We think of the LRA as starting at position 1 on an infinite tape and moving right in a sequence […]

CSC427 Spring 2018, HW #9 (extra credit) Mitsu Ogihara Due date: Monday, April 30 (10 points) Show that the polynomial-time mapping reducibility ≤pm is a transitive relation; that is, for all languages A, B, and C, A ≤pm B and B ≤pm C implies A ≤pm C. (10 points) Show that SAT cannot be polynomial-time

CSC427 Spring 2018, HW #8 Mitsu Ogihara Due date: Wednesday, April 17 (15 points) A positive integer n ≥ 2 is a prime number if and only if there is no integer d,2≤d≤n−1,suchthatddividesn. Showthatthelanguage{0p |pisaprime number } is in class P. (15 points) It is known that an odd number n is a prime number

COMP90057 Advanced Theoretical Computer Science Assignment 2 Second (Spring) Semester 2017 Posted on LMS: Friday, 22 September 2017 Due: Friday, 13 October 2017 [9:00am] Important: Your submissions for this assignment must be your own individual work. There is a further notice about this below. This document has two pages. Expect to spend about 10 hours

Monash University Faculty of Information Technology 2nd Semester 2017 FIT2014 Assignment 2 Finite Automata, Context-Free Languages, Lexical analysis, Parsing, Turing machines, Universality DUE: 11:55pm, Friday 6 October 2017 In these exercises, you will • implement lexical analysers using lex (Problem 3); • implement parsers using lex and yacc (Problems 1, 4); • practise using the

CS 3800 2016-10-27. Return this single, two-sided sheet. Your name: In this problem you will show that you cannot decide anything about the language of Turing machines. Formally, let P be a set of languages over the alphabet Σ = {0,1}. Let LP := {M : M is a TM and L(M) ∈ P}.Prove that