Question

Let $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{\Sigma }\mathbf{,}\mathbf{R}\mathbf{,}\mathbf{S}\mathbf{)}$be the following grammar. $\mathbf{V}\mathbf{=}\mathbf{\{}\mathbf{S}\mathbf{,}\mathbf{T}\mathbf{,}\mathbf{U}\mathbf{\}}\mathbf{;}\mathbf{\Sigma }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{\#}\mathbf{\}}\mathbf{;}$R is the set of rules:

$\begin{array}{l}\mathbf{S}\mathbf{\to }\mathbf{T}\mathbf{T}\mathbf{|}\mathbf{U}\\ \mathbf{T}\mathbf{\to }\mathbf{0}\mathbf{T}\mathbf{\left|}\mathbf{T}\mathbf{0}\mathbf{\right|}\mathbf{\#}\\ \mathbf{U}\mathbf{\to }\mathbf{0}\mathbf{U}\mathbf{00}\mathbf{|}\mathbf{\#}\end{array}$

a. Describe$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$ in English.

b. Prove that$\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$is not regular.

Short answer

1. The language is in English is described below.
2. $\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$is not regular language is proved.

Step-by-step solution

Define regular language

A language is regular if it can be expressed in terms of regular expression. A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings

Describe L(G) in English

$L\left(G\right)$is a set of strings of zeros and that either contain exactly 2$\#s$ and any number of zeros or contain exactly $1\#$and the number of 0s to the right of the$\#$ is twice the of zeros to the left.]

Prove that L(G) is not regular

The given grammar does not follow the property of a regular language, so this is not a regular language.

$L\left(G\right)$is not regular.

Let prove this using closure properties. Here consider the following sequence of languages.

Now consider a homomorphism,

$h1:\{0,1,\#\}\to \{0,\#\}$

such that,

$h1\left(0\right)=0,h1(\#)=\#,$ and $h1\left(1\right)=00.LetK1=h-11\left(L\left(G\right)\right).$

Let $K_2=K_1\cap L(0*\#1*).$

Observe that the only strings in $L\left(G\right)$that have a single $\#$symbol are those belonging to $L_2$(defined in the previous part), and given the definition of homomorphism h1,

Here let’s conclude that $K_2=\left\{0i\#1i|i\ge 0\right\}.$

Consider the homomorphism $h2:\{0,1,\#\}\to \{0,1\},whereh2\left(0\right)=0,h2\left(1\right)=1$

and then observe that $K3=h2\left(K2\right)=\left\{0^n{1}^n|n\ge 0\right\}$

Since $K1,K2,andK3$are obtained from$L\left(G\right)$ through regularity-preserving operations and $K3$is non-regular, we can conclude that$L\left(G\right)$ is not regular.

Hence,$L\left(G\right)$ is not regular language is proved.