Question

The syntax of the monkey languages is quite simple, yet only monkeys can speak it without making mistakes. The alphabet of the language is {a, b, d, #}, where # stands or a space. The grammar is

<stop> ::= b|d

<plosive> ::= <stop>a

<syllable> ::= <plosive>|<plosive><stop>|a<plosive>|a<stop>

<word> ::= <syllable>|<syllable><word><syllable>

<sentence> ::= <word>|<sentence>#<word>

Using parse trees, which of the following speakers is the secret agent masquerading as a monkey?

Chimp: abdabaadab#ada

Baboon: dad#ad#abaadad#badadbaad

Answer 1

Parse tree for Chimp:

String is: abdabaadab#ada

<sentence> = <sentence> # <word>

::= <word> # <word>

::= <syllable> <word> <syllable> # <word>

::= <syllable> <word> <syllable> # <syllable>

::= <syllable> <word> <syllable> # a <plosive>

::= <syllable> <word> <syllable> # a <stop> a

::= <syllable> <word> <syllable> # a d a

::= a <stop> <word> <syllable> # a d a

::= a b <syllable> <word> <syllable> <syllable> # a d a

::= a b <plosive> <word> <syllable> <syllable> # a d a

::= a b <stop> a <word> <syllable> <syllable> # a d a

::= a b d a <word> <syllable> <syllable> # a d a

::= a b d a <word> <syllable> <plosive> <stop> # a d a

::= a b d a <word> <syllable> <stop> a <stop> # a d a

::= a b d a <word> <syllable> d a b # a d a

::= a b d a <syllable> <syllable> d a b # a d a

::= a b d a <plosive> <syllable> d a b # a d a

::= a b d a <stop> a <syllable> d a b # a d a

::= a b d a b a <syllable> d a b # a d a

We are not able to get the string that Chimp is speaking here.

Parse tree for Baboon:

String is: dad#ad#abaadad#badadbaad

<sentence> ::= <sentence> # <word>

::= <sentence> # <word> # <word>

::= <sentence> # <word> # <word> # <word>

::= <plosive> <stop> # <word> # <word> # <word>

::= <stop> a <stop> # <word> # <word> # <word>

::= d a d # <word> # <word> # <word>

::= d a d # <syllable> # <word> # <word>

::= d a d # a <plosive> # <word> # <word>

::= d a d # a <stop> # <word> # <word>

::= d a d # a d # <word> # <word>

::= d a d # a d # <syllable> <word> <syllable> # <word>

::= d a d # a d # <syllable> <word> a <stop> # <word>

::= d a d # a d # <syllable> <syllable> a d # <word>

::= d a d # a d # <syllable> a <stop> a d # <word>

::= d a d # a d # <syllable> a d a d # <word>

::= d a d # a d # a <plosive> a d a d # <word>

::= d a d # a d # a <stop> a a d a d # <word>

::= d a d # a d # a b a a d a d # <word>

::= d a d # a d # a b a a d a d # <syllable> <word> <syllable>

::= d a d # a d # a b a a d a d # <plosive> <word> <syllable>

::= d a d # a d # a b a a d a d # <stop> a <word> <syllable>

::= d a d # a d # a b a a d a d # b a <word> a <stop>

::= d a d # a d # a b a a d a d # b a <word> a d

::= d a d # a d # a b a a d a d # b a <syllable> <word> <syllable> a d

::= d a d # a d # a b a a d a d # b a <syllable> <word> <plosive> a d

::= d a d # a d # a b a a d a d # b a <syllable> <word> <stop> a a d

::= d a d # a d # a b a a d a d # b a <plosive> <stop> <word> b a a d

::= d a d # a d # a b a a d a d # b a <stop> <stop> <word> b a a d

::= d a d # a d # a b a a d a d # b a d a d b a a d