Greibach NF transformation

• Previous message: Dr. Yongge Wang: "Re: Comparing two notions of computable number"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Sat, 28 Feb 2004 01:06:46 +0100

Hi,

I am trying to convert this grammar in CNF to Greibach normal form using the
algorithm explained in
http://cs.engr.uky.edu/~lewis/texts/theory/languages/cf-lang.pdf on page
6pp.:

S -> 0
S -> AA
A -> 1
A -> SS

I have done it like this but I am pretty unsure if I stepped through the
Algo correctly:

First lets enumerate the above variables:

A1 -> 1
A1 -> S2 S2
S2 -> 0
S2 -> A1 A1

Some rules are already OK and can be marked so:

(1) A1 -> 1
(2) S2 -> 0

Let the rule A1 -> S2 S2 be ok first since 1<2.
But the rule S2 -> A1 A1 has to be replaced now since 2>1:

First we use sustituton, which means that we check what we can get out of
the first A1 on the right side. As far as I understood we have to check for
ALL possibilities here. Hence, we get::

S2 -> 1 A1
S2 -> S2 S2 A1

The first of these rules is ok again:

(3) S2 -> 1 A1

But the rule S2 -> S2 S2 A1 has a left recursion:

We determine the S2 rules that start with S2 on the right and the ones that
do not start with S2 on the right. We find only ones that do not start with
S2 on the right, namely the rule:

S2 -> 1 A1

Hence we get the new rules due to left recursion elimination:

S2 -> 1 A1 S2'
S2' -> S2 A1
S2' -> S2 A1 S2'

One rule can be regarded OK again:

(4) S2 -> 1 A1 S2'

Since there are no more left recursions we can finish the algorithm by using
further subtitutions only:

The rule S2' -> S2 A1 leads to:

(5) S2' -> 0 A1, 1 A1 A1, 1 A1 S2' A1

The rule S2' -> S2 A1 S2' leads to:

(6) S2' -> 0 A1 S2', 1 A1 S2', 1 A1 S2' S2'

Finally, the rule A1 -> S2 S2 leads to:

(7) A1 -> 0 S2, 1 A1 S2, 1 A1 S2' S2

Summarizing we get the rules from (1)-(7):

A1 -> 1, 0 S2, 1 A1 S2, 1 A1 S2' S2
S2 -> 0, 1 A1, 1 A1 S2'
S2' -> 0 A1, 1 A1 A1, 1 A1 S2' A1, 0 A1 S2', 1 A1 S2' S2'

Have I done everything right ?
Does someone know another grammar in CNF which could be converted to GNF for
practicing (with a link to the solution of course) ?

Thanks a lot !

Regards,

Andreas

• Previous message: Dr. Yongge Wang: "Re: Comparing two notions of computable number"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]