2

I'm trying to discern whether or not I am answering this question correctly. If someone could shine some light on this, that would be greatly appreciated. So let's state for instance that we have the following phrase-structure grammar:

Which phrase-structure grammar will consist of only the bit strings 0,1, and 11? Maybe I'm overthinking this, but I assume the answer would be D. So here are the possible answers.

A. S->1A
   S->0B
   A->0
   B->1

From Option A, I don't see how it could be the answer as S->1A->10 or alternatively S->0B->01. 11 is not a part of that language.

B. S->1
   S->0A
   A->0S

From Option B, I don't see how this can be the answer as well the possible combinations all commence with 0, thus having an 11 as part of the language is impossible/improbable. Please correct me if I'm incorrect.

C. S->1A
   A->0B
   B->1A
   B->1B

Now from option C, I can see how this COULD BE an answer, however, there is no way to end a derivation with a number. Derivations all end with a letter.

D. S->0
   S->1
   S->11

This answer seems to be the most logical, but it also seems like a trick. All are S or starting symbols. Is this the correct answer? Thanks!

Linuxn00b
  • 29
  • Yes, D is the only correct answer, more or less for the reasons you said. C does not derive any strings: a derivation is incomplete until all nonterminal symbols are eliminated, and in C this never happens. B derives one string that does not begin with a zero, namely 1, but as you observed it does not derive11. (It also doesn't derive 0.) – MJD Nov 30 '16 at 02:49
  • Thanks for confirming MJD. – Linuxn00b Nov 30 '16 at 03:29

1 Answers1

1

Your answer is correct, that only grammar D generates the required language. And your explanations are mostly correct, except for a few minor errors.

For grammar B, you said “the possible combinations all commence with 0”, which is almost true, but grammar B also generates the string 1. But as you said, it fails to derive 11, so it isn't what is wanted. (It also derives 001, 00001, and so on.)

For grammar C, you said “derivations all end with a letter”. Usually some of the symbols are designated as “terminal” and the rest as “non-terminal”, and the language only includes sequences of terminal symbols. Sequences that include non-terminal symbols are unfinished. Sometimes the lists of terminal and non-terminal symbols are given explicitly, but when they aren't as in this case, you are supposed to assume that capital letters like A, B, and S are non-terminal, and digits and lowercase letters are terminal. All of this is by way of saying that the language derived by grammar C is actually empty and contains no strings at all: there is no way to finish any derivation!

But your idea of what is going on seems generally correct, and you did get the right answer to this tricky-seeming question.

MJD
  • 65,394
  • 39
  • 298
  • 580