1. Consider a language of words, where each word is a string of dots and dashes.

Question

1.      Consider a language of words, where each word is a string of dots and dashes.  The following grammar describes this language:

<word> = <dot>|<dash><word>|<word> <dot>

<dot> =

<dash> = --

a.       Write all three-character strings that are in this language.

b.      Is the string ???? - - in this language? Explain

c.       Write a seven-character string that contains more dashes than dots and is in the language.  Show how you know that your answer is correct.

d.      Write pseudocode for a recursive recognition function isIn(str) that returns true if the string str is in this language and returns false otherwise.

Explanation / Answer

Let's start listing the possible words. The only word consisting of one character is a single dot. By applying the second production rule, you can add a dash in front of the word, which gives you . If you apply the third rule instead, you add a dot after the first dot, resulting in .

So now I have two valid words consisting of two characters each:

-.
..

Now I can go on and apply the two production rules again to these two words, resulting in four three-character words. Of course, in the same way, you get 8 four-character words, 16 five-character words and so on.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.