CS 360 Introduction to the Theory of Computing Spring 2019 Assignment


CS 360 Introduction to the Theory of ComputingSpring 2019Assignment 3Due: Thursday, July 4On this assignment you will be asked to describe PDAs and DSMs that perform certain tasks.Please work hard to make your PDAs and DSMs as clear and simple as possible, be sure to cor-rectly use the notation described in the notes, and include helpful commentary if you believe itwill assist the grader in understanding your answer—for you may lose points if it is too difficultfor the grader to verify the correctness of your solutions, even if they turn out to be correct!1. [8 points] In this question, you are asked to provide descriptions of PDAs for two languagesover the binary alphabetΣ={0, 1}. The shorthand notation for PDAs introduced in Lecture 11may help to make your PDAs state diagrams more concise.(a) Describe a PDA that recognizes the languageA={w∈Σ∗:|w|0>|w|1}.Here, the notation|w|adenotes the number of times the symbolaappears inw.(b) Describe a PDA that recognizes the languageB={uv:u,v∈Σ∗,|u|=|v|,u6=v}.2. [8 points] For a given alphabetΣ, recall from Lecture 11 that we defineStack(Σ) ={↑,↓}×Σ,and we say that a stringw∈Stack(Σ)∗is avalid stack stringif, when it is read from left to right,it represents a legal sequence of pushes and pops for a single stack (where(↓,a)means “pushthe symbolaonto the stack” and(↑,a)means “pop the symbolaoff of the stack”). Note thata valid stack string does not need to result in an empty stack—the only thing that can make astack string invalid is that it attempts to either pop the wrong symbol or pop an empty stack.Prove that the languageA={w∈Stack(Σ)∗:wis not a valid stack string}is context-free.3. [8 points] Give the description of a DSMMhaving input alphabetΣ={0, 1}that operates asfollows:•If the input toMisε, thenMshouldreject.•If the input toMisx6=ε, thenMshouldaccept. Moreover, whenMaccepts, its inputstack (i.e., stack 0, orXif you prefer) should store the stringythat comes immediatelybeforexwith respect to the lexicographic ordering ofΣ∗.5 bonus points go to the person or persons having a correct solution with the smallest numberof states (including the accept state and reject state). You may use subroutines if you wish, butthey contribute the total number of states required to implement them.4. [1 point] For each of the questions above, list the full name of each of your 360 classmates withwhom you worked on that question. (If you didn’t work with anyone, that is fine: just indicatethat you worked alone.)1

The post CS 360 Introduction to the Theory of Computing Spring 2019 Assignment appeared first on mynursinghomeworks.


Source link