CISC/CMPE 223 (Software Specifications)
Winter 2025
Assignment II
Due Date: Friday, March 14, 2025, 11:59 PM
Total Marks: 100
Instructions:
1. Theory Answers: Please submit all answers in one document (PDF file format) for the written answers. You can write/type the answers and submit the document. But please make sure that all pages are merged in order/sequentially (problem 1 to problem 5) in one PDF file. The name of the pdf file should be theoryAn-swer.pdf
2. For the programming question, you can choose C or C++ or Java or Python. No other language will be accepted. please make sure that enough comments are given to understand your code and also provide a read me file explaining how to run your code and how to provide the input for your program.
3. Each programming solution should be in a separate folder. Make the folder name as the question name. For example: program 5 should be in a folder named, q5. This folder will contain the ‘read me’ file related to the question 5 and the code.
4. Finally make the submission folder under your last name and assignment no. For example, if your last name is choudhury, the folder name should be choudhuryAs-signment1. This folder will have the theoryAnswer.pdf and all programming ques-tions folder. Now, compresss this final submission folder, say, choudhuryAssign-ment1.zip and submit it.
5. Please be careful when submitting your files. Any files submitted after the dead-line will not be considered, and grading will be done on the last submitted file within the deadline. Make sure that your submitted files contain your final an-swers and that they are not corrupted. No requests to modify or replace submitted answers after the deadline will be entertained.
|
Problem 1
|
|
(2 × 10 = 20 marks)
Let Σ = {0, 1}, and let B be the collection of strings over Σ that contain at least one ‘0’ in their second half. Formally, def1ne
B = { uv | u ∈ Σ* , v ∈ Σ* 0 Σ* , |u| ≥ |v|}.
(a) Design a pushdown automaton (PDA), M that recognizes B. Write down your PDA,
M = (Q, Σ, Γ, δ, q0, F)
as a formal 6-tuple, with a fully labeled state diagram (transition graph), together with an explanation of how the stack is used and how each transition works as the transition function δ .
(b) Give a context-free grammar (CFG) that generates B.
|
|
Problem 2
|
|
(2 × 10 = 20 marks)
Let Σ = {0, 1}, and let c be a special symbol not in Σ . Def1ne the language
L = { w cwR | w ∈ Σ* },
where wR denotes the reverse of the string w. In other words, L is the collection of strings over the alphabet Σ ∪ {c} such that every string has exactly one c, splits the string into two parts w and wR , and these parts are reverses of each other.
(a) Design a pushdown automaton (PDA), M that recognizes B. Write down your PDA,
M = (Q, Σ, Γ, δ, q0, F)
as a formal 6-tuple, with a fully labeled state diagram (transition graph), together with an explanation of how the stack is used and how each transition works as the transition function δ .
(b) Give a context-free grammar (CFG) that generates L.
|
|
Problem 3
(20 marks)
Write a program (in C, C++, Java, or Python) that will simulate the PDA from Problem 2 and determine whether the PDA accepts an input string or NOT. Note that you need to implement the stack and transition function by yourself. Do not use any libraries. Your program should satisfy the following requirements:
|
|
1. The PDA should process an input string and determine whether it belongs to language L.
2. You should explicitly handle the stack operations (push, pop and others if any).
3. You must implement the transition function to manage state changes based on the input symbols and stack contents.
|
|
Problem 4
|
|
(20 marks)
Let Σ = {a, b}. Consider the set
L = { w x wR | w ∈ Σ* , x ∈ {a, b}, wR is w reversed}.
Each string in L has one symbol x ∈ {a, b} in the middle, with a substring w to the left and the reverse of w to the right.
Design a Turing Machine M that accepts exactly the strings in L (and rejects all other strings). Write down your TM as a formal 7-tuple (Q, Σ, Γ, δ, q0, qaccept , q reject) with a fully labeled state diagram (or transition graph) together with an explanation of how the tape is used and how each transition works as the transition function δ .
|
|
Problem 5
|
|
(2 × 10 = 20 marks)
(a) Give an implementation-level description of a Turing machine which decides the language {w | w does not contain (exactly) twice as many 0s as 1s}.
(b) Give an implementation-level description of a Turing machine which decides the language consisting of all strings of 0s whose length is a power of 2.
|