91Ó°ÊÓ

Context-free grammar is a notation used for describing languages. It is more powerful than finite automata or Regular expressions.

(a)

The capital letters are called variables because the value of that alphabet changes by replacing the productions.

Thus, the variables in the given grammar are,$\mathrm{V}=\{\mathrm{R},\mathrm{X},\mathrm{S},\mathrm{T}\}$.

Therefore, the variables are:$\mathrm{V}=\{\mathrm{R},\mathrm{X},\mathrm{S},\mathrm{T}\}$

(b)

The letters which are represented in small are called terminals. Thus, the terminals in the given grammar are, $\{\mathrm{a},\mathrm{b}\}$

Hence, the terminals are$\{\mathrm{a},\mathrm{b}\}$

(c)

The special nonterminal symbol which appears in the initial string generated by the given grammar.

Hence, the start variable is $\mathrm{R}$.

(d)

The three strings in language$\mathrm{L}\left(\mathrm{G}\right)$of grammar $\mathrm{G}$are as follows,

Proof:

Consider the production $\mathrm{R}→\mathrm{S}$,Replace $\mathrm{S}$with $\mathrm{a}\mathrm{Tb}$from the production $\mathrm{R}→\mathrm{aTb}$.Replace $\mathrm{T}$with $\mathrm{Î\mu }$ from the production $\mathrm{R}→\mathrm{²¹Î\mu ²ú}$. The resulting string is $\mathrm{R}→\mathrm{ab}$.

Therefore, the string is present in .

Proof:

Consider the production$\mathrm{R}→\mathrm{S}$,Replace$\mathrm{S}$ with $\mathrm{bTa}$from the production $\mathrm{R}→\mathrm{bTa}$. Replace $\mathrm{T}$with $\mathrm{Î\mu }$from the production $\mathrm{R}→\mathrm{²úÎ\mu ²¹}$.The resulting string is$\mathrm{R}→\mathrm{ba}$ .

Therefore, the string is present in.

Proof:

Consider the production$\mathrm{R}→\mathrm{S}$,Replace$\mathrm{S}$ with$\mathrm{aTb}$ from the production$\mathrm{R}→\mathrm{aTb}$ .Replace $\mathrm{T}$with $\mathrm{x}$from the production $\mathrm{R}→\mathrm{aXb}$. Replace$\mathrm{x}$ with$\mathrm{a}$ from the production$\mathrm{X}→\mathrm{a}$ .The resulting string is $\mathrm{R}→\mathrm{aab}$.

Hence, the three strings are$\mathrm{ab},\mathrm{ba}$ and$\mathrm{aab}$.

(e)

The three strings not in L(G) are

$\mathrm{aaa}$,$\mathrm{bab}$ , $\mathrm{bbb}$

Proof:

Substitute the production rules in variables, starting from the starts symbol. The above four strings cannot be obtained.

Hence, the strings $\mathrm{aaa}$, $\mathrm{bab}$,and$\mathrm{bbb}$ arenot in L (G).

(f)

$\mathrm{T}⇒\mathrm{aba}$

False because there is no rule which translates $T$directly to $\mathrm{aba}$.

Hence, the given statement is false.

(g)

$\mathrm{T}\stackrel{∗}{⇒}\mathrm{aba}$, can be produced by the production $\mathrm{T}→\mathrm{XTX}$. Thus, the given statement isTrue.

Hence,$\mathrm{T}\stackrel{∗}{⇒}\mathrm{aba}$ is true.

(h)

The grammar has no rule $\mathrm{T}⇒\mathrm{T}$.

Hence,$\mathrm{T}⇒\mathrm{T}$ is false.

(i)

The production $\mathrm{T}\stackrel{∗}{⇒}\mathrm{T}$can be derived from the given grammar. Thus, the given statement is True.

Hence,$\mathrm{T}\stackrel{∗}{⇒}\mathrm{T}$ is True.

(j)

The given production is true because each $\mathrm{X}$can be substituted with a or b.

Hence,$\mathrm{XXX}\stackrel{∗}{⇒}\mathrm{aba}$ is true.

(k)

The given rule is false since $\mathrm{X}$can only become a or b.

Hence,$\mathrm{X}\stackrel{∗}{⇒}\mathrm{aba}$ is false.

(l)

The given rule is true because as$\mathrm{T}$ can be substituted with an empty string $∈$.

Hence, $\mathrm{T}\stackrel{∗}{⇒}\mathrm{XX}$is true.

(m)

The given rule is true, since $\mathrm{T}⇒\mathrm{XTX}⇒\mathrm{XXX}$can be substituted with $\mathrm{X}$. $\mathrm{X}\stackrel{∗}{⇒}\mathrm{aba}$.

Hence, $\mathrm{T}\stackrel{∗}{⇒}\mathrm{XXX}$is true.

(n)

False because any string derived from $\mathrm{S}$has at least one occurrence of a and b.

Hence, role="math" localid="1660815034121" $\mathrm{S}\stackrel{*}{⇒}∈$is false.

(o)

Since from $\mathrm{R}$get any number of ${\mathrm{X}}^{\text{'}}$on both sides, $\mathrm{L}\left(\mathrm{G}\right)={\{\mathrm{a},\mathrm{b})}^{∗}\backslash ({\mathrm{a}}^{∗}∪{\mathrm{b}}^{∗})$. It produces strings of the form ${\mathrm{X}}^{\mathrm{n}}{\mathrm{SX}}^{\mathrm{n}}$for value of $\mathrm{n}$greater than or equal to 0.

Therefore, $\mathrm{L}\left(\mathrm{G}\right)$ consists of all strings over$\mathrm{a}$ and $\mathrm{b}$that are not palindromes.