Math Problems Vault

Example 4.15

Find a grammar $G$ such that $L(G)=\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$ .

?

Example 4.16

Find a grammar $G$ such that $L(G)=\left\{ a^{2^{n}} \mid n \geq 0\right\}$ .

?

Example 4.17

Find a grammar $G$ such that $L(G)=\left\{ w w \mid w \in \left\{ a, b\right\}^{*}\right\}$ .

?

Example 4.18

Find a grammar $G$ such that $L(G)=\left\{ a^{n} b^{m} c^{n m} \mid n, m \geq 0\right\}$ .

?

Problem 4.5.1

(a)(b)

Consider the grammar $G_{1}$ with nonterminals $V=\left\{ S, A, B, C\right\}$ , terminals $\Sigma = \left\{ a, b, c\right\}$ , and rules

\begin{array}{lll} S \longrightarrow A S B C \mid \varepsilon , & & \\ A B \longrightarrow B A, & A C \longrightarrow C A, & B A \longrightarrow A B, \\ B C \longrightarrow C B, & C A \longrightarrow A C, & C B \longrightarrow B C, \\ A \longrightarrow a, & B \longrightarrow b, & C \longrightarrow c. \end{array}

?

(a)

Show a derivation of string ccbaabcba.

(b)

What is $L\left(G_{1}\right)$ ? Give a brief argument for your answer.

Problem 4.5.2

(a)(b)

Consider the grammar $G_{2}$ with nonterminals $V=\left\{ S, A, L, L_{h}, R,[],\right\}$ , terminal $\Sigma =\left\{ a\right\}$ and rules

\begin{array}{rlr} S \rightarrow [A R a] \mid a, & R A \rightarrow A R, & R a \rightarrow a a R, \\ R] \longrightarrow L] \mid L_{h}, & A L \longrightarrow L A, & a L \longrightarrow L a, \\ {[L \longrightarrow [A R,} & a L_{h} \longrightarrow L_{h} a, & A L_{h} \longrightarrow L_{h} a, \\ {\left[L_{h} \longrightarrow \varepsilon .\right.} & & \end{array}

?

(a)

Show a derivation of $a^{6}$ .

(b)

What is $L\left(G_{2}\right)$ ? Give a brief argument for your answer.

Problem 4.5.3

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)

$\left\{ a^{n^{2}} \mid n \geq 0\right\} , x=a^{9}$ . [Hint: Following the idea of Exercise 2 above, generate, at the $k$ th iteration, a sentential form with $k$ copies of $A$ and $k^{2}-k$ copies of $a$ .]

(b)

$\left\{ a^{2^{n}-n} \mid n \geq 0\right\} , x=a^{5}$ .

(c)

$\left\{ a^{n^{2}+n} \mid n \geq 0\right\} , x=a^{11}$ .

(d)

$\left\{ a^{n^{3}+2 n^{2}-5 n+4} \mid n \geq 0\right\} , x=a^{34}$ . [Hint: Similar to part (a) above, generate, at the $k$ th iteration, a sentential form with $k$ copies of $A, k^{2}$ copies of $B$ , and $k^{3}+k^{2}-6 k+4$ copies of $a$ .]

(e)

$\left\{ a^{n} b^{2^{n}} a^{n} \mid n \geq 0\right\} , x=a^{3} b^{8} a^{3}$ .

(f)

$\left\{ a^{n} b^{n} a^{n} b^{n} \mid n \geq 0\right\} , x=a^{4} b^{4} a^{4} b^{4}$ .

(g)

$\left\{ w c z \mid w, z \in \left\{ a, b\right\}^{*}, w \neq z\right\} , x=a a b c a a b a$ .

(h)

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(w)>\#_{b}(w)>\#_{c}(w)\right\} , x=$ cbaabcbaa.

(i)

$\left\{ w^{n}\left|w \in \left\{ a, b\right\}^{*},\left|w\right|=n\right\} , x=a a b a a b a a b\right.$ .

Problem 4.5.4

(a)(b)

?

(a)

Find a grammar $G$ such that $w \xRightarrow [G]{*} w^{R}$ for all $w \in \left\{ a, b\right\}$ .

(b)

Find a grammar $G$ such that, for all $x, y \in \left\{ a, b\right\}^{*}$ with $\left|x\right|=\left|y\right|$ , $x y \xRightarrow [G]{*} y x$ .

Problem 4.5.5

(a)(b)(c)(d)

We consider a new computational model called Labeled Markov Algorithms (LMA). An LMA $M$ is defined as a triple $(\Sigma , \Gamma , P)$ , where $\Sigma$ is the input alphabet, $\Gamma$ is a working alphabet with $\Sigma \subseteq \Gamma$ , and $P$ is a program, consisting of a finite sequence $r_{1}, r_{2}, \ldots , r_{n}$ of instructions. Each instruction $r_{i}$ in $P$ is of the form

L_{i}: \alpha \rightarrow \beta ; \text{ goto } L_{j}

where $\alpha , \beta \in \Gamma^{*}$ , and $j$ is a positive integer ( $\alpha \rightarrow \beta$ is called a production rule and $L_{j}$ is called the next instruction label). An instruction ( $L_{i}$ : $\alpha \rightarrow \beta$ ; goto $L_{j}$ ;) can be applied to a string $w \in \Gamma^{*}$ if $\alpha$ is a substring of $w$ . The application of this instruction to $w$ produces a new string $x$ by replacing the leftmost occurrence of $\alpha$ in $w$ by $\beta$ .

On an input $w \in \Sigma^{*}$ , the LMA $M$ operates as follows: At any time of computation, it maintains a current sentential form $w$ and a current instruction label $L_{i}$ . Initially, $w$ is the input string and the current instruction label is $L_{1}$ . At each step, it finds the least integer $k \geq i$ , where $L_{i}$ is the current instruction label, such that instruction $r_{k}$ is applicable to $w$ . Then, it applies $r_{k}$ to $w$ to obtain a new sentential form $x$ . It resets $w$ to be $x$ , and resets the current instruction label $L$ to be the the next instruction label of $r_{k}$ . If no instruction $r_{k}$ , with $k \geq i$ , is applicable to the current sentential form $w$ , then the machine halts with output $w$ . (In particular, if the current instruction label is $L_{i}$ , with $i$ greater than the number $n$ of instructions in $P$ , then the machine halts.)

For any LMA $M$ , we let $L(M)=\left\{ x \in \Sigma^{*} \mid M\text{ halts on }x\right\}$ , We say $M$ computes a partial function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ , if $M$ halts on each input $x \in \operatorname {Domain}(f)$ with the final sentential form $w=f(x)$ , and $M$ does not halt on any $x \notin \operatorname {Domain}(f)$ .

?

(a)

Design an LMA $M$ that computes the function $f(x)=x^{R}$ for $x \in \left\{ a, b\right\}^{*}$ .

(b)

Show that every Turing-computable function $f$ is computable by an LMA.

(c)

Show that for any LMA $M, L(M)$ is Turing-acceptable.

(d)

Show that every partial function $f$ computed by an LMA $M$ is Turing-computable.