How do you create a sentential form in a given grammar? I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can actually be read. For example, under what circumstances can you read $abT$ in $S$? Can you skip past $aBS$ and go to $abT$ or $a$?
I understand that deciding whether $aBaabda$ can be produced is a theoretical question, so you can theoretically create anything as long as its within the bounds/rules of a language. But I don't fully understand the rules of producing a sentential form.
And on not understanding rules fully: can you stop reading input on a non-terminal? It's name, of course, implies not. For example, without creating a derivation tree can you tell that something like $aaaabdaaaaBS$ or $aabdaB$ can't be made because it ends in a non-terminal? Except, writing this I realised that a non-terminal such as $B$ has ϵ, so that implies you can end on $B$, right?
Or can you end simply when you have matched a sentential form? For example, if you create a derivation tree and have a node for $S$, do you have to carry on reading or can you simply end?
If you know how to decide whether a word belongs to the language generated by a grammar, then you can extend this to sentential forms, in the following way. For each nonterminal $A$, add a new terminal $\mathbf{A}$. Add rules $A \to \mathbf{A}$. Given a sentential form, replace each nonterminal $A$ with the terminal $\mathbf{A}$. Now ask whether the resulting word belongs to the language generated by the augmented grammar.
As an example, your grammar turns to
\begin{align}
S &amp;\to aBS \mid abT \mid a \mid \mathbf{S} \\
T &amp;\to d \mid dT \mid \mathbf{T} \\
B &amp;\to da \mid \epsilon \mid S \mid \mathbf{B}
\end{align}
The original grammar generates $aBaabda$ iff the augmented grammar generates $a\mathbf{B}aabda$.