4.5 Unrestricted Grammars 199
- Construct grammars for each of the following languages. Also show (i)
the derivation of the given string x: and (ii) a proof of why your grammar
does not generate any string not in the language.
(a) {an2 1 n > 0}, x = ug. [Hint: Following the idea of Exercise
2 above, generate, at the kth iteration, a sentential form with k:
copies of A and k2 - k copies of a.]
(b) {Use+ 1 n 2 0}, x = u5.
0 {
(:I -I
un2+n 1 n > - 0}, II: = a”.
un3+2n2-5n+4 1 n > 0}, x = u34. [Hint: Similar to part (a) above,generate, at the kth iteration, a sentential form with k copies of
A, k2 copies of B, and k3 + k2 - 6k + 4 copies of a.]
(e) {unb2nun I n > 0}, x = u3b8u3.
(f) {unbnunbn I n> 0}, x = u4b4u4b4.
(g) {WC2 I w, zi e (a, Q*, w # z>, x = uubcuubu.
(h) {w E {u,b,c}* I #a(w) > #b(w) > #c(w)}, x = cbuubcbuu.
(i) {w” I w E {a, b}*, lull = n}, x = uubuubuub.- (a) Find a grammar G such that w & wR for all w E {a, b}.
G
(b) Find a grammar G such that, for all x, y e {a, b} with 1x1 = 1~~1,
xy =$2 yx - We consider a new computational model called Labeled Murkov AZgo-
rithms (LMA). An LMA M is defined as a triple (C, I’, P), where C
is the input alphabet, I’ is a working alphabet with C C - I?, and P is
a program, consisting of a finite sequence Tr, r2,... , Yn of instructions.
Each instruction ri in P is of the form
where a, ,8 E I’*, and j is a positive integer (al -+ p is called a production
rule and Lj is called the next instruction label). An instruction (Li :
a + ,0 ; goto Lj ; ) can be applied to a string w E I* if a is a substring
of w. The application of this instruction to w produces a new string x
by replacing the leftmost occurrence of cx in w by ,&
On an input w E C*, the LMA M operates as follows: At any time
of computation, it maintains a current sentential form w and a current
instruction label Li. Initially, w is the input string and the current
instruction label is L1. At each step, it finds the least integer k > - i,
where Li is the current instruction label, such that instruction rk is
applicable to w. Then, it applies rk to w to obtain a new sentential
form 1x3. It resets w to be x, and resets the current instruction label L
to be the the next instruction label of rk. If no instruction rk, with
k > - i, is applicable to the current sentential form w, then the machine