Question

Let $\mathbf{PREFIX}-{\mathbf{FREE}}_{\mathrm{REX}}=$role="math" localid="1659933266276" $\mathbf{\left\{}\mathbf{\left\{}\mathbf{R}\mathbf{\right\}}\mathbf{|}\mathbf{R}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{regular}\mathbf{}\mathbf{expression}\mathbf{}\mathbf{and}\mathbf{}\mathbf{L}\mathbf{\left(}\mathbf{R}\mathbf{\right)}\mathbf{}\mathbf{is}\mathbf{}\mathbf{prefix}\mathbf{-}\mathbf{free}\mathbf{\right\}}$. Show that $\mathbf{PREFIX}\mathbf{-}{\mathbf{FREE}}_{\mathbf{REX}}$is decidable. Why does a similar approach fail to show that$\mathbf{PREFIX}\mathbf{-}{\mathbf{FREE}}_{\mathbf{CFG}}$ is decidable?

Short answer

$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{REX}}=\left\{\left\{\mathrm{R}\right\}|\mathrm{R}\mathrm{is}\mathrm{a}\mathrm{regular}\mathrm{expression}\mathrm{and}\mathrm{L}\left(\mathrm{R}\right)\mathrm{is}\mathrm{prefix}-\mathrm{free}\right\}$

$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{REX}}$is decidable.

$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{CFG}}=\left\{\left\{\mathrm{R}\right\}|\mathrm{R}\mathrm{is}\mathrm{a}\mathrm{regular}\mathrm{expression}\mathrm{and}\mathrm{L}\left(\mathrm{R}\right)\mathrm{isprefix}-\mathrm{free}\right\}$

$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{CFG}}$is not decidable.

Step-by-step solution

Step 1: Prefixed regular expression.

A prefixed regular expression (PRE) is defined recursively that is given as,

• Empty set $\varphi$ end empty string ""- are PREs
• For each symbol $a$ in alphabet, " $\mathrm{a}$" is a PRE
• If $\mathrm{p}\mathrm{and}\mathrm{q}$are PREs denoting the regular sets $\mathrm{p}\mathrm{and}\mathrm{q}$, respectively, $\mathrm{r}$ is a regular expression denoting the regular set$\mathrm{R}$ such that e belongs to $\mathrm{R}$, and x belongs to the string , then the following expressions are also PREs:
  • $\mathrm{p}+\mathrm{q}\left(\mathrm{union}\right)$
  • $\mathrm{xp}(\mathrm{concatenation}\mathrm{with}\mathrm{symbol}\mathrm{x}\mathrm{on}\mathrm{the}\mathrm{left}).$
  • $pr(\mathrm{concatenation}\mathrm{with}\mathrm{an}\mathrm{e}-\mathrm{regular}\mathrm{on}\mathrm{the}\mathrm{right})$
  • $\mathrm{p}*\left(\mathrm{star}\right).$
    
    

Proving that the given grammar is inherently ambiguous grammar.

$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{REX}}=\left\{\left\{\mathrm{R}\right\}|\mathrm{R}\mathrm{i}\mathrm{sa}\mathrm{regular}\mathrm{expression}\mathrm{and}\mathrm{L}\left(\mathrm{R}\right)\mathrm{isprefix}-\mathrm{free}\right\}$.

Here , for the solution A prefixed regular expression (PRE) is defined recursively that is given as, the language in the regular expression Empty set $\mathrm{\varphi }$ end empty string are PREs. And here for each symbol $\mathrm{a}$ in alphabet, " $\mathrm{a}$" is a PRE. Another condition for the regular expression If $\mathrm{p}\mathrm{and}\mathrm{q}$are PREs denoting the regular sets $\mathrm{p}\mathrm{and}\mathrm{q}$, respectively, $\mathrm{r}$ is a regular expression denoting the regular set $\mathrm{R}$such that e belongs to $\mathrm{R}$, and x belongs to the string , then the following expressions are also PREs: for these terms the expression is to be follow this statement $\mathrm{p}+\mathrm{q}\left(\mathrm{union}\right)$$\mathrm{pr}(\mathrm{concatenation}\mathrm{with}\mathrm{an}\mathrm{e}-\mathrm{regular}\mathrm{on}\mathrm{the}\mathrm{right})$and $\mathrm{p}*\left(\mathrm{star}\right).$must follow the the regular expression hence the given language follow all the condition so, it is a decidable.

Hence, $\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{REX}}=\left\{\left\{\mathrm{R}\right\}|\mathrm{R}\mathrm{is}\mathrm{a}\mathrm{regular}\mathrm{expression}\mathrm{and}\mathrm{L}\left(\mathrm{R}\right)\mathrm{is}\mathrm{prefix}-\mathrm{free}\right\}$, $\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{REX}}$is decidable.

In the given question there is an another question is to evaluate the given language is decidable or not now, the expression is given as,

role="math" localid="1659934276289" $\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{CFG}}=\left\{\left\{\mathrm{R}\right\}|\mathrm{R}\mathrm{is}\mathrm{a}\mathrm{regular}\mathrm{expression}\mathrm{and}\mathrm{L}\left(\mathrm{R}\right)\mathrm{is}\mathrm{prefix}-\mathrm{free}\right\}$

Here , for the solution A prefixed context free grammar is defined recursively that is given as, the language in the context free grammar Empty set $\mathrm{\varphi }$ end empty string are PREs. And here for each symbol $\mathrm{a}$ in alphabet, " role="math" localid="1659934358918" $\mathrm{a}$" is a context free grammar. Another condition for the regular expression If $\mathrm{p}\mathrm{and}\mathrm{q}$are context free grammar denoting the regular sets $\mathrm{p}\mathrm{and}\mathrm{q}$, respectively, $\mathrm{r}$is a regular expression denoting the regular set$\mathrm{R}$such that e belongs to$\mathrm{R}$, $\mathrm{xp}(\mathrm{concatenation}\mathrm{with}\mathrm{symbol}\mathrm{x}\mathrm{on}\mathrm{the}\mathrm{left}).$and x belongs to the string , then the following expressions are also context free grammar: for these terms the expression is to be follow this statement $\mathrm{p}+\mathrm{q}\left(\mathrm{union}\right)$

$\mathrm{pr}(\mathrm{concatenation}\mathrm{with}\mathrm{an}\mathrm{e}-\mathrm{regular}\mathrm{on}\mathrm{the}\mathrm{right})$and$\mathrm{p}*\left(\mathrm{star}\right).$ is not follow the the context free grammar hence the given language follow all the condition so, it is a not decidable expression.

Hence ,$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{CFG}}=\left\{\left\{\mathrm{R}\right\}|\mathrm{R}\mathrm{is}\mathrm{a}\mathrm{regular}\mathrm{expression}\mathrm{and}\mathrm{L}\left(\mathrm{R}\right)\mathrm{isprefix}-\mathrm{free}\right\}$

$\mathrm{PREFIX}-{\mathrm{FREE}}_{\mathrm{CFG}}$is not decidable.