grammarrdp

Which of the following language satisfies the grammar?

I'm kinda new to RDP/Pairwise Disjoint Test and this is just a sample problem. I already have the answer and I would just like to verify if this is correct.

Grammar:

<GU> ::= du<GU>bi<MI> | <HO> | ru
<MI> ::= ra | fa | <HO>
<HO>::= bi<HO> | bi

Solution:

will generate a sting of "bi" OR one "bi" will generate one "ra" OR one "fa" OR (string of "bi" OR one "bi")

So will generate

du <GU> bi {ra | fa | {bi's | bi} } | {bi's | bi} | ru

Here are the sentences that can be produced by the grammar:

a. dudurubifabira
b. dubibibira
c. dubirubirurafa
d. dududubibibifabirabibibi
e. dududubibifarabirabibi

My answer is "b" and "d".

Am I correct?

Solution

  • Looks like a can also be generated by the language:

       <GU>
-> du<GU>bi<MI>
-> dudu<GU>bi<MI>bi<MI>
-> dudurubi<MI>bi<MI>
-> dudurubifabi<MI>
-> dudurubifabira

    Otherwise, your end result seems to be correct. I'd be careful about saying a "bi" will generate something though, since it's a terminal.