I am having some problems with Phrase Structure Grammar (formula being let G = (V, T, S, P) where V is a finite vocabulary, T is a subset of V, and S is a start symbol from V, and P are productions (set of Pairs of Strings). I just don't understand it. It was not well-explained to me. Could someone kindly show me how it works by assessing the following problem in a step by step procedure:
"Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, S}, T={0, 1} and set of productions P consisting of S->1S, S->00A, A->0A and A->0
Select all of the following that belong to this language.
A.1000
B.11000
C.11001
D.111000"
Thanks in advance!
I'll solve A and C for you; hopefully it will help you understand the derivations for B and D.
A:
$S \to 1S$; We do this first because the string starts with a $1$, and the $1$ doesn't appear in any rule but this one.
$1S \to 100A$; this is the only way to get a $0$ from an $S$.
$100A \to 1000$; and the string is completed. Therefore, we can derive $1000$ for this grammar.
C:
$S \to 1S \to 11S \to 1100A$; we follow similar logic as before about getting certain letters. However, it doesn't look like we can get a $1$ character after "leaving" the $S$ non-terminal. And we have to leave the $S$ non-terminal in order to get the $0$ character. So it looks like we can't derive the string $11001$ in this grammar.