Algorithm算法代写代考

Algorithms for CFLs Thursday, February 25, 2021 11:41 AM

Reductions in Computability Theory Prakash Panangaden 22nd March 2021 The concept of reduction is central to computability and complexity theory. The phrase “P reduces to Q” is often used in a confusing way. In this note I will clarify how it is used and explain the difference between two different notions of reduction: many-one reduction

A set that is neither CE nor co-CE Prakash Panangaden 22nd March 2021 Proposition 1. If Q ≤m P and if P is CE then so is Q. If P is co-CE so is Q. Proof . Suppose that f is the required mapping reduction: then w ∈ Q if and only if f(w) ∈

2/25/2021 OneNote https://mcgill-my.sharepoint.com/personal/prakash_panangaden_mcgill_ca/_layouts/15/Doc.aspx?sourcedoc={4ebabb6a-e289-462f-821b-913836894465}&action=e… 1/6 Algorithms for CFLs Thursday, February 25, 2021 11:41 AM 2/25/2021 OneNote https://mcgill-my.sharepoint.com/personal/prakash_panangaden_mcgill_ca/_layouts/15/Doc.aspx?sourcedoc={4ebabb6a-e289-462f-821b-913836894465}&action=e… 2/6 2/25/2021 OneNote https://mcgill-my.sharepoint.com/personal/prakash_panangaden_mcgill_ca/_layouts/15/Doc.aspx?sourcedoc={4ebabb6a-e289-462f-821b-913836894465}&action=e… 3/6 2/25/2021 OneNote https://mcgill-my.sharepoint.com/personal/prakash_panangaden_mcgill_ca/_layouts/15/Doc.aspx?sourcedoc={4ebabb6a-e289-462f-821b-913836894465}&action=e… 4/6 2/25/2021 OneNote https://mcgill-my.sharepoint.com/personal/prakash_panangaden_mcgill_ca/_layouts/15/Doc.aspx?sourcedoc={4ebabb6a-e289-462f-821b-913836894465}&action=e… 5/6 2/25/2021 OneNote https://mcgill-my.sharepoint.com/personal/prakash_panangaden_mcgill_ca/_layouts/15/Doc.aspx?sourcedoc={4ebabb6a-e289-462f-821b-913836894465}&action=e… 6/6

The Myhill-Nerode Theorem Prakash Panangaden 2nd February 2021 The collection of strings over an alphabet Σ, i.e. Σ∗ is an infinite set1 with a binary operation called concatenation and written by placing the arguments next to each other as in xy; occasion- ally we write x · y when we want to emphasize the operation.

COMP 330 Winter 2021 Assignment 2 Solutions Prakash Panangaden Question 1[20 points] Give regular expressions for the following languages over {a, b}: 1. {w|w contains an even number of occurrences of a} 2. {w|w contains an odd number of occurrences of b} 3. {w| does not contain the substring ab} 4. {w| does not contain

COMP 330 Winter 2021 Mid-term Examination School of Computer Science McGill University Answers due by 13th February 2021 8:00am This examination is open book. You have 60 minutes. There are 3 questions on two pages. Please write your answers in a pdf file and upload it. The upload will be under the assignments tab. Automata

COMP 330 Winter 2021 Mid-term Examination Solutions Prakash Panangaden February 4, 2021 Question 1[40 points] In this question the alphabet is fixed as {a, b}. • Write a regular expression for the language of strings containing a’s only when they occur as part of a block of consecutive a’s of even length. Thus the legal