FORMAL LANGUAGE & AUTOMATA THEORY

The language:

$$L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \}$$

is:

(i) regular
(ii) context-free but not regular
(iii) context-sensitive but not context-free
(iv) type-0 but not context-sensitive

The language $\{ a^n b^n c^{n+m} \mid m, n \ge 1 \}$ is:

(i) regular
(ii) context-free but not regular
(iii) context-sensitive but not context-free
(iv) type 0 but not context-sensitive

Which production is not allowed in a CSG?

(i) $AB \rightarrow BA$
(ii) $A \rightarrow \epsilon$
(iii) $A \rightarrow a$
(iv) $a B \rightarrow a b$

Prove that every context-free language is context-sensitive, but the converse is not true. Support your answer with a suitable language example.

Given the following context-sensitive grammar:
$S \rightarrow aSBC | abc$
$CB \rightarrow BC$
$aB \rightarrow ab$
$bB \rightarrow bb$
$bC \rightarrow bc$
$cC \rightarrow cc$

Identify the language generated by the grammar. Derive the string aabbcc step by step.

Define a Linear Bounded Automaton (LBA). Design an LBA that accepts the language $L = \{a^n b^n c^n | n \ge 1\}$. Explain how tape length is restricted.