Math Problems Vault

Example 6.33

Find a context-sensitive grammar for the language

L=\left\{ a^{2^{n}} \mid n \geq 0\right\}

?

Example 6.34

Find a context-sensitive grammar for the language

L=\left\{ a^{n^{2}} \mid n \geq 1\right\}

?

Problem 6.5.1

Construct context-sensitive grammars for the languages of Examples 4.17 and 4.18, and for the languages in Exercises 3(b)-3(i) of Section 4.5.

?

Problem 6.5.2

Complete the last part of the proof of Theorem 6.35. That is, describe how to attach the leftmost and rightmost blanks to their neighboring symbols to convert grammar $G_{2}$ to a context-sensitive grammar.

?

Problem 6.5.3

Show that the class of context-sensitive languages is closed under union, intersection, concatenation, and Kleene closure.

?

Problem 6.5.4

Find a recursive language $L$ that is not context-sensitive.

?

Problem 6.5.5

What is wrong if we use the following simpler algorithm to compute $N_{k}$ in the proof of Theorem 6.36?

For each $k$ , to compute $N_{k}$ , we generate each configuration $\alpha \in C_{x}$ one by one and, for each one, nondeterministically verify whether $\operatorname {reach}(\beta , \alpha , k)$ (by machine $M_{1}$ ), and increments the counter for $N_{k}$ by one if $\operatorname {reach}(\beta , \alpha , k)$ holds.

?

Problem 6.5.6

Recall, from Exercise 6 of Section 3.5, the notion of 2-stack PDA's. Show that each language accepted by a 2 -stack PDA is a context-sensitive language.

?