CSE 354 - Automata Theory and Formal Languages
HOMEWORK 3
Due date: PS. Hour 16.12.2014
1) Design a PDA for 𝒂𝒊 𝒃𝒋 𝒄𝒌 𝒊 = 𝒋 𝒐𝒓 𝒋 = 𝒌
2) Convert the grammer below to CNF
𝑺 → 𝒂𝑺𝒃 𝑨𝒂 𝑩𝒃 | 𝑨
𝑨 → 𝒂𝑨
𝑩 → 𝒃𝑩 | 𝜺
3) Using the grammer G below, use the CYK algorithm to
determine whether string “aabab” is in L(G) or not.
S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a