4
$\begingroup$

I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out in particular:

V: { S, A, B, C }
T: { a, b, c }
P: {
    S -> aA | λ | ASA
   AA -> aA | a
}

My professor described the result as "any number of as". This makes sense if you never use the first S or AA rule; you can simply replace S with ASA as many times as you like, then replace each S with λ (getting some even-length string of As); you can then replace all AAs with as.

But what if I picked the first rule? So, I start with S, then replace S with aA. I now have a string that contains neither S, nor AA, so the final terminal string should be aA. (This could also be done with S -> ASA -> AA -> aA.)

Is this allowed? If so, what is the result called? Since it still contains a variable, is this just a rejected/invalid result?

NB: I did ask my professor about this. He explicitly said to "ignore the first rules of each 'S' and 'AA'", and could not give me any further explanation on why to do this.

$\endgroup$
  • 1
    $\begingroup$ You can apply any rule in the set of productions $P$. The result is called a sentential form. A sentential form belongs to the language recognized by the grammar if it consists of terminal symbols only. $\endgroup$ – saadtaame Sep 14 '12 at 18:41
  • $\begingroup$ @saadtaame Okay, that makes perfect sense. Thanks! $\endgroup$ – Eric Sep 14 '12 at 18:45
  • $\begingroup$ I wrote an answer. I'll extend it if you need an algorithm for removing variables that derive no terminal strings. $\endgroup$ – saadtaame Sep 14 '12 at 18:53
  • $\begingroup$ @saadtaame I saw your answer (and upvoted appropriately), but I don't believe I need a way to determine non-terminal strings; my question was more centered around whether or not these strings are important, rather than how to find them. Thanks, though! :) $\endgroup$ – Eric Sep 14 '12 at 18:58
9
$\begingroup$

When you are given a grammar $G$, then the language it produces, $L(G)$, is all the (finite) words it can generate. All the other "derivations" that don't yield any legal word, can be ignored.

For instance, for the grammar $G_1$:

S -> SS | Sa | aS

the language that the grammar produces is $L(G_1)=\emptyset$, as no derivation ever terminates.

$\endgroup$
  • $\begingroup$ I would assume, then, that aA is not a "legal word" if A has no rule defined such that it can reach an element of $T$? $\endgroup$ – Eric Sep 14 '12 at 18:40
  • 3
    $\begingroup$ Indeed, $aA$ is not a "word" since it contains a non-terminal. A word can contain only terminals. If there is no production (better, a sequence of productions) that can take $A$ into a string of terminals, then $aA$ will never yield a valid word for that grammar $\endgroup$ – Ran G. Sep 14 '12 at 18:46
  • $\begingroup$ Assumedly this follows from the quantification in the logic of the formal definition of a formal grammar. I'd be curious to see that made more precise. $\endgroup$ – asmeurer Sep 14 '12 at 22:22
  • $\begingroup$ Strings that may contain terminals as well as non-terminals are called sentences. By definition, the generated language consists of all sentences that only have terminals. So all the "illegal" strings fall away automagically. Try not to think of it as algorithmically applying rules; that may not even terminate. $\endgroup$ – Raphael Sep 15 '12 at 14:17
3
$\begingroup$

You can apply any rule in the set of productions P. The result is called a sentential form. A sentential form belongs to the language recognized by the grammar if it consists of terminal symbols only. Variables that derive no terminal strings can be removed safely (without changing the language).

$\endgroup$

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.