Description

CSE340: Theory of Computation (Homework Assignment 3)
Total Number of Pages: 1 Total Points 50

Question 1. You are given two strings a,b ∈ {0,1}∗ and you need to check whether they are equal or not. However, you are living in an age, where computers are still not invented, pushdown automata are the only computing devices that you have at your disposal. You create a strategy to test whether or not a = b. Instead of directly checking a = b, you first check whether the length of the strings are equal or not. If the lengths are unequal then you have a 6= b.
(a) (5 points) Design a language to check whether or not |a| = |b|. Design a PDA which accepts this language, which would solve your problem.
(b) (2 points) If |a| = |b|, then you have to check whether a actually equals b or not by comparing each alphabet. Come up with the language for this problem.
(c) (8 points) Can you design a PDA for the language you designed in part B? If not then prove that a PDA cannot be designed for the language.
Question 2. (15 points) Prove that the language L = {anbjck | k = jn, j,k,n ≥ 0} is not context free. Question 3. (a) (10 points) Design a CFG to generate the following language,
{aibjck | i = j or i 6= k, where i,j,k ≥ 0}
Clearly explain the working of the non terminal symbols that you have used.
(b) (10 points) Convert the following CFG into an equivalent CFG in Chomsky normal form

Page 1 of 1