Subject: Theory of Computer Science

Topic: Basic Concepts & Finite Automata

Difficulty: Medium

i) There are no $\epsilon$ moves so we can directly solve step ii)

ii) every symbol in $\alpha$ is production of the form where $|\alpha| \geq 2$ should be a variable

This can be done by adding 2 production

$c_{a}\rightarrow a$ $c_{b}\rightarrow b$

The production set becomes often changes

S- Cax|Cby |ca|cb

X= Cas|Cbs|Cb

y - Cax|Cbs

iii) finding equivalence CNF original production

original production

$S \rightarrow Cax$

$S \rightarrow Cby$

$Ca \rightarrow Ca$

$Cb \rightarrow Cb$

$X \rightarrow Cas$

$S \rightarrow Cby$

$Cb \rightarrow b$

$y \rightarrow Cax$

$y \rightarrow Cbs$

Equivalence Production

$S \rightarrow Cax$

$S \rightarrow Cby$

$Ca \rightarrow a$

$Cb \rightarrow b$

$X \rightarrow Cby$

$Cb \rightarrow b$

$y \rightarrow Cax$

$y \rightarrow Cbs$