Principle programming language Assignment | Get Homework Help

 

CSCI3136
Assignment 6
Instructor: Alex Brodsky
Due: 9:00am, Friday, June 26, 2020
1. [10 marks] Give a deterministic pushdown automata (DPDA) that recognizes the language
L = {xny2n | n ! 0}
Provide a brief explanation of how the DPDA works.
2. [10 marks] Give a deterministic pushdown automata (DPDA) that recognizes the language
L = {xiyjwkz` | 0  i < j, 0  k < `}
Provide a brief explanation of how the DPDA works.
3. [10 marks] Give a deterministic pushdown automata (DPDA) that recognizes the language
L = {xiwkz`yj | 0  i < j, 0  k < `}
Provide a brief explanation of how the DPDA works.
4. [10 marks] Give a pushdown automata (PDA) that recognizes the language
L = {” 2 {0, 1}⇤ | ” 6= “r}
I.e., the language of words that are not palindromes.
Provide a brief explanation of how the PDA works.
5. [10 marks] Our definition of a PDA specifies that a PDA can pop zero or one symbols
from its stack and can push zero or one symbols onto its stack during a transition. I.e., the
transition function is defined as
# : Q ⇥ (⌃ [ {✏}) ⇥ (” [ {✏}) ! Q ⇥ (” [ {✏})
A generalized pushdown automata (GPDA) can pop and push any fixed number of symbols
from/on its stack during a single transition. I.e., its trasition function is defined as
# : Q ⇥ ⌃ [ {✏} ⇥ “⇤ ! Q ⇥ “⇤
Notice that all PDAs are also GPDAs.
Show that PDAs and GPDAs can recognize exactly the same set of languages. I.e., that for
any GPDA, we can construct a PDA that recognizes the same language.
1
CSCI3136 Summer 2020 Assignment 6
Marking Scheme
1. Marking scheme for Questions 1, 2, 3, and 4.
3 points 2 points 1 point 0 points
States No missing states 1 missing state
More than 1 missing
state
No automaton provided
Transitions
No missing transitions
1 or 2 missing transitions
More than 2 missing
transitions
No automaton provided
Correctness
Automaton recognizes
the language
Automaton mostly
recognizes the language
Automaton does
not recognize the
language
Explanation
Explanation of automaton
makes sense
Partial explanation
provided
Explanation makes
no sense or not provided
2. Marking scheme for Question 5
4 points 3 points 2 points 1 point 0 points
Technique
Appropriate
technique used
Technique will
work with more
work
Technique can
be used for part
of the proof
Technique is inappropriate
for
this proof
No proof provided
Argument
Proof has no
gaps
Proof has a 1 or
2 minor gaps
Proof has a major
gap
Proof has several
major gaps
No proof provided
Neatness
Proof is easy to
read
Proof is readable
Proof is illegible
or no proof provided
2
CSCI3136: Assignment 6
Summer 2020
Student Name Login ID Student Number Student Signature
Mark
Question 1 /10
Question 2 /10
Question 3 /10
Question 4 /10
Question 5 /10
Total /50
Comments:
Assignments are due by 9:00am on the due date. Assignments must be submitted electronically
via Brightspace. Please submit a PDF for the written work. You can do your work on paper
and then scan in and submit the assignment.
Plagiarism in assignment answers will not be tolerated. By submitting their answers to this
assignment, the authors named above declare that its content is their original work and that
they did not use any sources for its preparation other than the class notes, the textbook, and
ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported
to the Facultys Academic Integrity O

Don't use plagiarized sources. Get Your Custom Essay on
Principle programming language Assignment | Get Homework Help
Just from $13/Page
Order Essay
Homework On Time
Calculate the Price of your PAPER Now
Pages (550 words)
Approximate price: -

Why Choose Us

Top quality papers

We always make sure that writers follow all your instructions precisely. You can choose your academic level: high school, college/university or professional, and we will assign a writer who has a respective degree.

Professional academic writers

We have hired a team of professional writers experienced in academic and business writing. Most of them are native speakers and PhD holders able to take care of any assignment you need help with.

Free revisions

If you feel that we missed something, send the order for a free revision. You will have 10 days to send the order for revision after you receive the final paper. You can either do it on your own after signing in to your personal account or by contacting our support.

On-time delivery

All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension. In case you cannot provide us with more time, a 100% refund is guaranteed.

Original & confidential

We use several checkers to make sure that all papers you receive are plagiarism-free. Our editors carefully go through all in-text citations. We also promise full confidentiality in all our services.

24/7 Customer Support

Our support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.

Try it now!

Calculate the price of your order

Total price:
$0.00

How it works?

Follow these simple steps to get your paper done

Place your order

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

Receive the final file

Once your paper is ready, we will email it to you.

Our Services

No need to work on your paper at night. Sleep tight, we will cover your back. We offer all kinds of writing services.

Essays

Essay Writing Service

You are welcome to choose your academic level and the type of your paper. Our academic experts will gladly help you with essays, case studies, research papers and other assignments.

Admissions

Admission help & business writing

You can be positive that we will be here 24/7 to help you get accepted to the Master’s program at the TOP-universities or help you get a well-paid position.

Reviews

Editing your paper

Our academic writers and editors will help you submit a well-structured and organized paper just on time. We will ensure that your final paper is of the highest quality and absolutely free of mistakes.

Reviews

Revising your paper

Our academic writers and editors will help you with unlimited number of revisions in case you need any customization of your academic papers