Chapter 11

Construct a NDFSA that accepts the language generated by the regular grammar \(G=(N, T, P, \sigma),\) where: $$\begin{aligned}&N=| \sigma, \mathbf{A}, \mathbf{B}\\}, T=\\{\mathbf{a}, \mathbf{b}\\}, \text { and } P=\\{\sigma \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{a} \mathbf{A}, \mathbf{A} \rightarrow \mathbf{b B}, \mathbf{B} \rightarrow\\\ &\mathrm{bB}, \mathrm{A} \rightarrow \mathrm{a}\\} \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}\\}.\) Identify the language \(L(G)\)

Construct a NDFSA that accepts the language generated by the regular grammar \(G=(N, T, P, \sigma),\) where: $$\begin{aligned}&N=\\{\sigma, \mathrm{A}, \mathrm{B}\\}, T=\\{\mathrm{a}, \mathrm{b}\\}, \text { and } P=\\{\sigma \rightarrow \mathrm{a} \mathrm{A}, \sigma \rightarrow \mathrm{b} \mathrm{A}, \mathrm{A} \rightarrow \mathrm{aB}, \sigma \rightarrow\\\ &\mathbf{b}, \mathbf{B} \rightarrow \mathbf{b}\\} \end{aligned}$$

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma \mathbf{b}, \sigma \rightarrow \mathbf{a b}\\} .\) Determine if each word belongs to \(L(G).\) abba

Construct a NDFSA that accepts the language generated by the regular grammar \(G=(N, T, P, \sigma),\) where: \(N=\\{\sigma, \mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathrm{b} \sigma, \sigma \rightarrow \mathrm{a} \mathrm{A}, \mathrm{A} \rightarrow \mathrm{a} \mathrm{A}\) \(\mathrm{A} \rightarrow \mathrm{bB}, \mathrm{B} \rightarrow \mathrm{aA}, \mathrm{B} \rightarrow \mathrm{bC}, \mathrm{C} \rightarrow \mathrm{aD}, \mathrm{C} \rightarrow \mathrm{b} \sigma, \mathrm{D} \rightarrow \mathrm{aD}, \mathrm{D} \rightarrow \mathrm{bD}, \mathrm{C} \rightarrow\) af

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{a, b\\},\) and \(P=\\{\sigma \rightarrow a \sigma b, \sigma \rightarrow a b\\} .\) Determine if each word belongs to \(L(G)\) . $$\mathrm{abab}$$

Characterize the language recognized by the FSAs.

Arrange the binary words of each length in increasing order.Length two. Length two.

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma \mathbf{b}, \sigma \rightarrow \mathbf{a b}\\} .\) Determine if each word belongs to \(L(G).\) abab

Construct a NDFSA that accepts the language generated by the regular grammar \(G=(N, T, P, \sigma),\) where: $$\begin{aligned} &N=\\{\sigma, \mathrm{A}, \mathrm{B}, \mathrm{C}\\}, T=\\{\mathrm{a}, \mathrm{b}\\}, \text { and } P=\\{\sigma \rightarrow \mathrm{b} \sigma, \sigma \rightarrow \mathrm{a} \mathrm{A}, \mathrm{A} \rightarrow \mathrm{a} \mathrm{A}\\\ &\mathrm{A} \rightarrow \mathrm{bB}, \mathrm{B} \rightarrow \mathrm{aA}, \mathrm{B} \rightarrow \mathrm{bC}, \mathrm{C} \rightarrow \mathrm{aA}, \mathrm{C} \rightarrow \mathrm{b} \sigma, \mathrm{B} \rightarrow \mathrm{b}\\} \end{aligned}$$

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{a, b\\},\) and \(P=\\{\sigma \rightarrow a \sigma b, \sigma \rightarrow a b\\} .\) Determine if each word belongs to \(L(G)\) . $$\mathrm{a}^{2} \mathrm{b}^{2}$$

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma \mathbf{b}, \sigma \rightarrow \mathbf{a b}\\} .\) Determine if each word belongs to \(L(G).\) $$a^{2} b^{2}$$

A ternary word is a word over the alphabet \(\\{0,1,2\\} .\) Arrange the ternary words of each length in increasing order. Length one

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{a, b\\},\) and \(P=\\{\sigma \rightarrow a \sigma b, \sigma \rightarrow a b\\} .\) Determine if each word belongs to \(L(G)\) . $$\mathrm{a}^{3} \mathrm{b}^{3}$$

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma \mathbf{b}, \sigma \rightarrow \mathbf{a b}\\} .\) Determine if each word belongs to \(L(G).\) $$a^{3} b^{3}$$

A ternary word is a word over the alphabet \(\\{0,1,2\\} .\) Arrange the ternary words of each length in increasing order. Length two

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: Contain at least one \(a\)

Consider the grammar \(G=(N, T, P, \sigma),\) where \(N=\\{\sigma\\}, T=\\{\mathrm{a}, \mathrm{b}\\},\) and \(P=\\{\sigma \rightarrow \mathbf{a} \sigma \mathbf{b}, \sigma \rightarrow \mathbf{a b}\\} .\) Determine if each word belongs to \(L(G).\) Identify the language \(L(G)\)

Find the language generated by each grammar \(G=(N, T, P, \sigma)\) where:$$N=\\{\sigma, \mathrm{A}, \mathrm{B}\\}, T=\\{\mathrm{a}, \mathrm{b}\\}, P=\\{\sigma \rightarrow \mathrm{a} \mathrm{A}, \mathrm{A} \rightarrow \mathrm{Bb}, \mathrm{A} \rightarrow \mathrm{a}, \mathrm{B} \rightarrow \mathrm{b}\\}$$

Let \(\Sigma\) be a nonempty alphabet. Prove that \(\Sigma^{*}\) is infinite. (Hint: Assume \(\Sigma^{*}\) is finite. since \(\Sigma \neq \emptyset,\) it contains an element \(a .\) Let \(x \in \Sigma^{*}\) with largest length. Now consider \(x a .\) )

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: Begin with aa.

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: End with \(b b\)

Find the language generated by each grammar \(G=(N, T, P, \sigma)\) where: $$\begin{array}{l} N=\\{\sigma, \mathrm{A}, \mathrm{B}\\}, T=\\{\mathrm{a}, \mathrm{b}\\}, P=\\{\sigma \rightarrow \mathrm{a} \mathrm{Aa}, \mathrm{A} \rightarrow \mathrm{bBb}, \sigma \rightarrow \lambda, \mathrm{A} \rightarrow \mathrm{a}, \\ \mathrm{B} \rightarrow \mathrm{a}, \mathrm{B} \rightarrow \mathrm{b}\\} \end{array}$$

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: Contain \(a b a\) as a substring.

Develop a grammar that generates each language over {0,1}. $$\\{1,11,1111,11111111, \ldots\\}$$

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: Contain \(a^{3}\) as a substring.

Let \(A=\\{a, b c\\}\) and \(B=\\{\lambda, a b, b c\\} .\) Find each concatenation. \(A^{2}\)

Develop a grammar that generates each language over {0,1}. $$\\{0,00,10,100,110,0000,1010, \ldots\\}$$

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: Begin with \(a a\) or \(b b\)

Develop a grammar that generates each language over {0,1}. The set of words with prefix 00.

Create a NDFSA that accepts the regular language over \(\\{a, b\\}\) of strings that: Contain \(b a^{2} b\) as a substring.

Develop a grammar that generates each language over {0,1}. The set of words with suffix \(11 .\)

Create a NDFSA that accepts the regular language over \(\\{\mathrm{a}, \mathrm{b}\\}\) of strings that: Begin with \(a a\) , but not end in \(b b.\)

Create a NDFSA that accepts the regular language over \(\\{\mathrm{a}, \mathrm{b}\\}\) of strings that: Begin with \(a a\) and end in \(b b.\)

Create a grammar to produce each language over \(\\{\mathrm{a}, \mathrm{b}\\}\). $$\left\\{b^{n} a b^{n} | n \geq 0\right\\}$$

Let \(m\) denote the number of \(a\) 's in a string. Design an FSA that accepts strings over \(\\{a, b\\}\) which: Contain exactly one \(a.\)

Let \(A=\\{a, b c\\}\) and \(B=\\{\lambda, a b, b c\\} .\) Find each concatenation. \(A(B \cup C)=A B \cup A C\)

Create a grammar to produce each language over \(\\{a, b\\}\). $$\left\\{b^{n} a b^{n} | n \geq 0\right\\}$$

Create a grammar to produce each language over \(\\{\mathrm{a}, \mathrm{b}\\}\). $$\left\\{a^{n} b | n \geq 1\right\\}$$

Let \(m\) denote the number of \(a^{\prime} s\) in a string. Design an FSA that accepts strings over \(\\{a, b\\}\) which: Begin with \(a a\)

Let \(m\) denote the number of \(a\) 's in a string. Design an FSA that accepts strings over \(\\{a, b\\}\) which: Begin with \(a a.\)

Create a grammar to produce each language over \(\\{a, b\\}\). $$\left\\{\mathbf{a}^{n} \mathbf{b} | n \geq 1\right\\}$$

Create a grammar to produce each language over \(\\{\mathrm{a}, \mathrm{b}\\}\). $$\left\\{\mathbf{a}^{n} \text { bal } n \geq 1\right\\}$$

VCreate a grammar to produce each language over \(\\{a, b\\}\). $$\left\\{\mathrm{a}^{n} \mathrm{ba} | n \geq 1\right\\}$$

Create a grammar to produce each language over \(\\{\mathrm{a}, \mathrm{b}\\}\). $$\left\\{\mathbf{a}^{m} \mathbf{b}^{n} | m, n \geq 1\right\\}$$

Let \(m\) denote the number of \(a^{\prime} s\) in a string. Design an FSA that accepts strings over \(\\{a, b\\}\) which: Contain aaa as a substring.

Let \(m\) denote the number of \(a\) 's in a string. Design an FSA that accepts strings over \(\\{a, b\\}\) which: Contain aaa as a substring.

Create a grammar to produce each language over \(\\{a, b\\}\). $$\left\\{\mathbf{a}^{m} \mathbf{b}^{n} | m, n \geq 1\right\\}$$

Design an FSM accepting strings over \(\\{\mathrm{a}, \mathrm{b}\\}\) that: Contain \(a a\) as a sub string.

Create a grammar to produce each language over \(\\{\mathrm{a}, \mathrm{b}\\}\). The set of palindromes.