Final report

Notice: please submit your report to e-Learning@NDHU websit before 6/20(dead line).

Q1

A. Find context-free grammars for the language

$L=\{a^n{b}^m{c}^k:k=|n-m|\}$.

B. Find the GNF of

$L$ and then, construct an NPDA that accept the lanuage

$L$

Q2

A. Show that the language

$L=\{w\in \{a,b,c{\}}^{\ast }:n_a(w)=n_b(w)\ge n_c(w)\}$ is not context free.

B. Construct Turing machines that will accept the language

$L$.