Disclaimer: This serves as a document to help you understand
Theoretical Computer Science III
COS3701
2023
Assignment 2
School of Computing
Disclaimer: This serves as a document to help you understand
your assignment. Do not Plagiarize
BARCODE
, Disclaimer: This serves as a document to help you understand
Question 1 [15]
Build a DPDA to show that the language L = {(ab)n(ba)naa | n > 0} is deterministic
context free.
Question 2 [15]
Prove that the language L = {anb3nan} is non-context free. Use the pumping lemma
with length.
~ According to the pumping lemma with length any word w in L with more than 2p
characters can be broken up into five parts, i.e. the word can be written as w =
uvxyz, with length(vxy) <= 2p and length(x) > 0 and length(v) + length(y) > 0 and
where all words of the form uvnxynz with n > 1 are also in the language.
Theoretical Computer Science III
COS3701
2023
Assignment 2
School of Computing
Disclaimer: This serves as a document to help you understand
your assignment. Do not Plagiarize
BARCODE
, Disclaimer: This serves as a document to help you understand
Question 1 [15]
Build a DPDA to show that the language L = {(ab)n(ba)naa | n > 0} is deterministic
context free.
Question 2 [15]
Prove that the language L = {anb3nan} is non-context free. Use the pumping lemma
with length.
~ According to the pumping lemma with length any word w in L with more than 2p
characters can be broken up into five parts, i.e. the word can be written as w =
uvxyz, with length(vxy) <= 2p and length(x) > 0 and length(v) + length(y) > 0 and
where all words of the form uvnxynz with n > 1 are also in the language.
