Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)

0 votes
18 views
Find context-sensitive grammars for the following languages.

$(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$.

$(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.

Related questions

0 votes
0 answers
1
28 views
Find the context-sensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$. $\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$. $\text{(c)}$ $L=\{a^{n}b^mc^{n}d^m : n\geq 1, m\geq1\}$. $\text{(d)}$ $L=\{ww : w\in \{a,b\}^+\}$. $\text{(e)}$ $L=\{a^{n}b^nc^{n}d^m : n\geq 1\}$.
0 votes
0 answers
2
31 views
Without explicitly constructing it, show that there exists a context-sensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,|w|\geq|u|\}$.
0 votes
0 answers
3
13 views
$\text{Theorem}:$ Every context-sensitive language $L$ is recursive. For $m$ in Theorem, give explicit bounds for $m$ as a function of $|w|$ and $|V\cup T|$.
0 votes
0 answers
4
18 views
Show that the family of context-sensitive languages is closed under reversal.