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?

  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Oct 30 '20 at 12:20
  • $\begingroup$ Yeah, I understand that. But S⇒∗α implies it ends on a terminal, right? If so, that answers one of my questions. $\endgroup$ – Jake Jackson Oct 30 '20 at 12:22
  • $\begingroup$ Wikipedia contains a formal definition of "$S \Rightarrow^* \alpha$". This is all you need to know. You can answer your own questions. $\endgroup$ – Yuval Filmus Oct 30 '20 at 12:23
  • $\begingroup$ 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. $\endgroup$ – Jake Jackson Oct 30 '20 at 12:38

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.