Question

Let G be the following grammar:

$\begin{array}{l}\mathbf{S}\mathbf{\to }\mathbf{T}\mathbf{-}\mathbf{|}\\ \mathbf{T}\mathbf{\to }\mathbf{T}\mathbf{a}\mathbf{T}\mathbf{b}\mathbf{\left|}\mathbf{T}\mathbf{b}\mathbf{T}\mathbf{a}\mathbf{\right|}\mathbf{\epsilon }\end{array}$

1. Show that$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{w}\mathbf{-}\mathbf{\left|}\mathbf{\right|}\mathbf{w}\mathbf{\text{\hspace{0.17em}contains\hspace{0.17em}equal\hspace{0.17em}number\hspace{0.17em}of\hspace{0.17em}}}{\mathbf{a}}^{\mathbf{\text{'}}}\mathbf{\text{s\hspace{0.17em}and\hspace{0.17em}}}{\mathbf{b}}^{\mathbf{\text{'}}}\mathbf{\text{s}}\mathbf{\right\}}$ . Use a proof by induction on the length of W.
2. Use the DK-test to show that G is a DCFG,
3. Describe a DPDA that recognizes$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$

Short answer

1. It can be shown that the language given is the length of the by induction method.
2. DK-test shows that is a DCFG.
3. 
   

Step-by-step solution

Explain Context-free grammar

Context-free grammar that defines the productions that defines the context free language.

Step 2:Use a proof by induction on the length of W. 

a.

Consider the given grammar ,

$\begin{array}{l}S\to T-|\\ T\to TaTb\left|TbTa\right|\epsilon \end{array}$

Induction can be done by any of the side of the induction. From the above grammar, knowing that the terminals have epsilon.

Consider the string W contains $aabb$. Every string is generated by the grammar G is in L.

$aabb\to aaSbb\to aSb\to S\to T-|$

Therefore, it is been proved that any language G contain equal number of ’s and b’s in given strings.

Step 3:Use the DK-test to show that G is a DCFG,

b.

Consider the grammar, $L\left(G\right)=\left\{w-\left|\right|w\text{\hspace{0.17em}contains\hspace{0.17em}equal\hspace{0.17em}number\hspace{0.17em}of\hspace{0.17em}}{a}^{\text{'}}\text{s\hspace{0.17em}and\hspace{0.17em}}{b}^{\text{'}}\text{s}\right\}$, contains an equal number of a’s and b ’s.

If $uv$is one of the valid string with prefix u that will end as$uv$ . In case of DCFG all the handles are being forces, so if $uv$is one of the valid string then that will end for handling$u{v}^{\text{'}}$ . Thus, the DK must be capable if handling all the accept states, but without outgoing path conditions.

The construction of the DK-test , concludes that G is deterministic, if the property of accept state is satisfied. Construct NFA to construct DFA, and find that there is no outgoing path is found from the start state.

Consider the valid string, and it handles $uv$, after the reduction of the rule, it becomes $T\to u,v$

K contains the path from start to end state. Give the input $x=uv$, been read after the transition and shift the string. After shifting , it is been found that there exists no outgoing state.

Therefore, Using DK-test it is proved that the grammar belongs to DCFG.

Step 4:Describe a DPDA that recognizesL(G)

c)

The DPDA that recognizes the$L\left(G\right)$is as follows,

Therefore,The DPDA that recognizes the$L\left(G\right)$has been obtained.