Chapter 11

In the grammar \(G=(N, T, P, \sigma), N=\\{\text { (sentence), (noun phrase), (verb), }\) \(\langle\text { object phrase }\rangle,\langle\text { article }\rangle,\langle\text { noun }\rangle \\}, T=\\{a, \text { the, cat, dog, chicken, milk, drinks, }\) eats \(\\}, \sigma=\langle\text { sentence }\rangle\) and the production rules are: $$\langle\text {sentence}\rangle \rightarrow \langle\text {noun phrase}\rangle \langle\text {verb}\rangle \langle\text {object phrase}\rangle$$ $$\langle\text {noun phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ $$\langle\text {article}\rangle \rightarrow a | \text { the }$$ $$\langle\text { noun }\rangle \rightarrow cat : dog | chicken : milk $$ $$\langle\text { verb }\rangle \rightarrow drinks | eats $$ $$\langle\text {object phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ Determine if each is a valid sentence in \(\mathrm{L}(\mathrm{G})\) The cat drinks the milk.

A language L over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L=\left\\{x \in \Sigma^{*} | x \text { begins with and ends in } b .\right\\}\)

Determine if each is a valid sentence in \(\mathrm{L}(\mathrm{G}).\) The cat drinks the milk.

In the grammar \(G=(N, T, P, \sigma), N=\\{\text { (sentence), (noun phrase), (verb), }\) \(\langle\text { object phrase }\rangle,\langle\text { article }\rangle,\langle\text { noun }\rangle \\}, T=\\{a, \text { the, cat, dog, chicken, milk, drinks, }\) eats \(\\}, \sigma=\langle\text { sentence }\rangle\) and the production rules are: $$\langle\text {sentence}\rangle \rightarrow \langle\text {noun phrase}\rangle \langle\text {verb}\rangle \langle\text {object phrase}\rangle$$ $$\langle\text {noun phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ $$\langle\text {article}\rangle \rightarrow a | \text { the }$$ $$\langle\text { noun }\rangle \rightarrow cat : dog | chicken : milk $$ $$\langle\text { verb }\rangle \rightarrow drinks | eats $$ $$\langle\text {object phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ Determine if each is a valid sentence in \(\mathrm{L}(\mathrm{G})\) A chicken eats the dog.

Determine if each is a valid sentence in \(\mathrm{L}(\mathrm{G}).\) The dog swallows the cat.

A language \(L\) over \(\Sigma=\\{a, b\\}\) is given. Find five words in each language. \(L\) is defined recursively as follows: (i) \(\lambda \in L\) (ii) \(x \in L \rightarrow a x b \in L\)

In the grammar \(G=(N, T, P, \sigma), N=\\{\text { (sentence), (noun phrase), (verb), }\) \(\langle\text { object phrase }\rangle,\langle\text { article }\rangle,\langle\text { noun }\rangle \\}, T=\\{a, \text { the, cat, dog, chicken, milk, drinks, }\) eats \(\\}, \sigma=\langle\text { sentence }\rangle\) and the production rules are: $$\langle\text {sentence}\rangle \rightarrow \langle\text {noun phrase}\rangle \langle\text {verb}\rangle \langle\text {object phrase}\rangle$$ $$\langle\text {noun phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ $$\langle\text {article}\rangle \rightarrow a | \text { the }$$ $$\langle\text { noun }\rangle \rightarrow cat : dog | chicken : milk $$ $$\langle\text { verb }\rangle \rightarrow drinks | eats $$ $$\langle\text {object phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ Construct a derivation tree for each sentence in \(L(G)\) . The cat eats the chicken.

Define each language \(L\) over the given alphabet recursively. The language \(L\) of all palindromes over \(\Sigma=\\{a, b\\} .\) (A palindrome over \(\Sigma\) is a word that reads the same both forwards and backwards. For instance, abba is a palindrome.)

The language \(L\) of all palindromes over \(\Sigma=\\{a, b\\} .\) (A palindrome over \(\Sigma\) is a word that reads the same both forwards and backwards. For instance, \(a b b a\) is a palindrome.

In the grammar \(G=(N, T, P, \sigma), N=\\{\text { (sentence), (noun phrase), (verb), }\) \(\langle\text { object phrase }\rangle,\langle\text { article }\rangle,\langle\text { noun }\rangle \\}, T=\\{a, \text { the, cat, dog, chicken, milk, drinks, }\) eats \(\\}, \sigma=\langle\text { sentence }\rangle\) and the production rules are: $$\langle\text {sentence}\rangle \rightarrow \langle\text {noun phrase}\rangle \langle\text {verb}\rangle \langle\text {object phrase}\rangle$$ $$\langle\text {noun phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ $$\langle\text {article}\rangle \rightarrow a | \text { the }$$ $$\langle\text { noun }\rangle \rightarrow cat : dog | chicken : milk $$ $$\langle\text { verb }\rangle \rightarrow drinks | eats $$ $$\langle\text {object phrase}\rangle \rightarrow \langle\text { article }\rangle\langle\text { noun }\rangle$$ Construct a derivation tree for each sentence in \(L(G)\) . A dog drinks the milk.

Define each language \(L\) over the given alphabet recursively. \(L=\left\\{a^{n} b^{n} | n \in N\right\\}, \Sigma=\\{a, b\\}\)

Define each language \(L\) over the given alphabet recursively. \(L=\\{0,00,10,100,110,0000,1010, \ldots\\}, \Sigma=\\{0,1\\}\)

Define each language \(L\) over the given alphabet recursively. \(L=\) set of binary representations of positive integers, \(\Sigma=\\{0,1\\}\)

Define each language \(L\) over the given alphabet recursively. \(L=\\{1,11,111,1111,11111, \ldots\\}, \Sigma=\\{0,1\\}\)

Define each language \(L\) over the given alphabet recursively. \(L=\left\\{x \in \Sigma^{*} | x=b^{n} a b^{n}, n \geq 0\right\\}, \Sigma=\\{a, b\\}\)

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 17 in Section 11.3

Define each language \(L\) over the given alphabet recursively. \(L=\) set of words over \(\Sigma=\\{0,1\\}\) with prefix 00

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 18 in Section 11.3

Define each language \(L\) over the given alphabet recursively. \(L=\) set of words over \(\Sigma=\\{0,1\\}\) with suffix 11

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 36 in Section 11.3

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 37 in Section 11.3

Construct a transition table for each FSM.

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 38 in Section 11.3

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{a, b\\},\) and \(P=\\{\sigma \rightarrow a \sigma, \sigma \rightarrow a A, A \rightarrow b\\},\) to answer Exercises \(15-23\) . Draw a derivation tree for each word in \(L(G)\) . $$\mathrm{ab}$$

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 40 in Section 11.3

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: Contain at least one \(a\).

Let \(L\) be the language recognized by an FSA and \(L^{R}=\left\\{x_{n} \ldots x_{1} \text { i } x_{1} \ldots x_{n} \in\right.\) L). Construct an NDFSA that accepts \(L^{R}\) from each FSA.(Hint: Reverse the directions of the edges; switch the roles of the initial state and the accepting states.) Exercise 41 in Section 11.3

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma, \sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b}\\}.\) Draw a derivation tree for each word in \(L(G).\) $$a^{2} b$$

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: Begin with \(a a\).

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{a, b\\},\) and \(P=\\{\sigma \rightarrow a \sigma, \sigma \rightarrow a A, A \rightarrow b\\},\) to answer Exercises \(15-23\) . Draw a derivation tree for each word in \(L(G)\) . $$\mathrm{a}^{3} \mathrm{b}$$

Using Example 11.1 , determine if each is a well-formed and fully parenthesized arithmetic expression. \((((x+y) /(((x-y) * z) \uparrow z))\)

Draw the transition diagram of the FSA, \(M=\left(S, A, I, f, s_{0}\right),\) where \(I=\) \(\\{\mathrm{a}, \mathrm{b}\\},\) and: $$\begin{array}{rl} S=\left\\{s_{0}, s_{1}, s_{2}\right\\}, \quad A=\left\\{s_{2}\right\\} \\ f\left(s_{0}, \mathrm{a}\right)=s_{0} & f\left(s_{0}, \mathrm{b}\right)=s_{1} \quad f\left(s_{1}, \mathrm{a}\right)=s_{0} \quad f\left(s_{1}, \mathrm{b}\right)=s_{2} \\ f\left(s_{2}, \mathrm{a}\right)=s_{0} & f\left(s_{2}, \mathrm{b}\right)=s_{2} \end{array}$$

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: End with \(b b\).

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{a, b\\},\) and \(P=\\{\sigma \rightarrow a \sigma, \sigma \rightarrow a A, A \rightarrow b\\},\) to answer Exercises \(15-23\) . Draw a derivation tree for each word in \(L(G)\) . $$\mathrm{a}^{4} \mathrm{b}$$

Using Example 11.1 , determine if each is a well-formed and fully parenthesized arithmetic expression. \((x \uparrow((y-x) \uparrow(-z)))\)

Draw the transition diagram of the FSA, \(M=\left(S, A, I, f, s_{0}\right),\) where \(I=\) \(\\{a, b\\},\) and: \(S=\left\\{s_{0}, s_{1}, s_{2}, s_{3}\right\\}, A=\left\\{s_{3}\right\\}\) \(\begin{array}{ll}{f\left(s_{0}, \mathbf{a}\right)=s_{1}} & {f\left(s_{0}, \mathbf{b}\right)=s_{0}} \\ {f\left(s_{2}, \mathbf{a}\right)=s_{1}} & {f\left(s_{2}, \mathbf{b}\right)=s_{3}}\end{array}\) \(\begin{array}{ll}{f\left(s_{1}, \mathbf{a}\right)=s_{1}} & {f\left(s_{1}, \mathbf{b}\right)=s_{2}} \\ {f\left(s_{3}, \mathbf{a}\right)=s_{1}} & {f\left(s_{3}, \mathbf{b}\right)=s_{0}}\end{array}\)

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma, \sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b}\\}.\) Draw a derivation tree for each word in \(L(G).\) $$a^{4} b$$

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: Contain \(a b a\) as a substring.

Using Example 11.1 , determine if each is a well-formed and fully parenthesized arithmetic expression. \((y+(z \uparrow(+x)) /(-x))\)

Draw the transition diagram of the FSA, \(M=\left(S, A, I, f, s_{0}\right),\) where \(I=\) \(\\{\mathrm{a}, \mathrm{b}\\},\) and: $$\begin{aligned} &S=\left\\{s_{0}, s_{1}, s_{2}, s_{3}\right\\}, A=\left\\{s_{2}\right\\}\\\ &\begin{array}{|c||cc|} \hline & {\boldsymbol{f}} \\ \hline \boldsymbol{S/I} & \mathbf{a} & \mathbf{b} \\ \hline {s_{0}} & s_{0} & s_{1} \\ s_{1} & s_{1} & s_{2} \\ s_{2} & s_{2} & s_{3} \\ s_{3} & s_{3} & s_{3} \\ \hline \end{array} \end{aligned}$$

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: Contain \(a a a\) as a substring.

Using Example 11.1 , determine if each is a well-formed and fully parenthesized arithmetic expression. \(((x-(y \uparrow z)) *(x+(y \uparrow(+z))))\)

Draw the transition diagram of the FSA, \(M=\left(S, A, I, f, s_{0}\right),\) where \(I=\) \(\\{\mathrm{a}, \mathrm{b}\\},\) and: $$\begin{aligned} &S=\left\\{s_{0}, s_{1}, s_{2}, s_{3}, s_{4}\right\\}, A=\left\\{s_{3}\right\\}\\\ &\begin{array}{|c||cc|} \hline & {\boldsymbol{f}} \\ \hline \boldsymbol{S} & \boldsymbol{a} & \mathbf{b} \\ \hline \boldsymbol{s}_{0} & \boldsymbol{s}_{1} & \boldsymbol{s}_{\boldsymbol{4}} \\ \boldsymbol{s}_{1} & \boldsymbol{s}_{\boldsymbol{4}} & \boldsymbol{s}_{2} \\ \boldsymbol{s}_{2} & \boldsymbol{s}_{\boldsymbol{3}} & \boldsymbol{s}_{\boldsymbol{4}} \\ \boldsymbol{s}_{\boldsymbol{3}} & \boldsymbol{s}_{\boldsymbol{3}} & \boldsymbol{s}_{\boldsymbol{3}} \\ \boldsymbol{s}_{\boldsymbol{4}} & \boldsymbol{s}_{\boldsymbol{4}} & \boldsymbol{s}_{\boldsymbol{4}} \\ \hline \end{array} \end{aligned}$$

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma, \sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b}\\}.\) Do the following words belong to \(L(G) ?\) abba

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: Begin with \(a a\) or \(b b\).

Define the set of words \(S\) over an alphabet \(\Sigma\) recursively. (Hint: Use concatenation.)

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma, \sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b}\\}.\) Do the following words belong to \(L(G) ?\) Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma, \sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b}\\}.\) Do the following words belong to \(L(G) ?\) $$a^{3} b$$

By making a DFSA, define a regular grammar \(G=(N, T, P, \sigma)\) that generates the language consisting of strings over \(\\{a, b\\}\) that: Contain \(b a a b\) as a substring.

Define the language \(L\) of all binary representations of non-negative integers recursively.

Use the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{A, \sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma, \sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b}\\}.\) Do the following words belong to \(L(G) ?\) $$a^{5} b$$