# 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?

• I suggest reviewing class materials. They should contain a full definition of how words (and sentential forms) are produced in a grammar. Alternatively, take a look at the Wikipedia definition. A grammar produces a sentential form $\alpha$ if $S \Rightarrow^* \alpha$. – Yuval Filmus Oct 30 '20 at 12:20
• Yeah, I understand that. But S⇒∗α implies it ends on a terminal, right? If so, that answers one of my questions. – Jake Jackson Oct 30 '20 at 12:22
• Wikipedia contains a formal definition of "$S \Rightarrow^* \alpha$". This is all you need to know. You can answer your own questions. – Yuval Filmus Oct 30 '20 at 12:23
• I am not here to get people to answer my worksheets. All I want to do is have a discussion about things, to learn about it properly. I don't know about you, but asking questions on forums provides way better answers than just trudging through Wikipedia. I have seen that definition before but I don't understand it as much as I would like. Hence why I am here. – Jake Jackson Oct 30 '20 at 12:38

## 1 Answer

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 &\to aBS \mid abT \mid a \mid \mathbf{S} \\ T &\to d \mid dT \mid \mathbf{T} \\ B &\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$$.