Prove that the following language is NOT regular by using the Pumping Lemma of regular language:
Prove that the following language is NOT regular by using MyHill-Nerode Theorem:
Design a Pushdown Automata (PDA) to accept the following language: Please explain your Push Down Automata step by step. Is your deterministic? Verify your answer, please.
Write down the context free grammar for the language of Problem 4. Can this language be generated by an un-ambiguous context free grammar?
Prove that the following language is not context free by using the Pumping Theorem of Context Free Language:
Design a Turing Machine (TM) to decide the following language by using machine schema: Is the TM a Linear Bounded Automata (LBA)? Justify your answer by counting the size of memory cells used in your algorithm.