Eliminating Unit Productions

312 Views Asked by At

Eliminate all unit-productions from the grammar:

$S \rightarrow abA\:|\:A\:|\:B$

$A \rightarrow B\:|\:ba\:|\:aBA$

$B \rightarrow A\:|\:aa\:|\:aA$

An article I was reading said that a unit production was one whose right side consisted of exactly one variable. But this is not the case for any of these right? So is it already simplified?

1

There are 1 best solutions below

0
On

When you write something like $$S \to abA\,|\, A \,|\, B$$ that is actually an abbreviation for three separate productions $$S \to abA$$ $$S \to A$$ $$S \to B$$ The last two are unit productions, since their right side consists of exactly one variable.