debugModerate
What if a formal grammar cannot be terminated?
Viewed 0 times
cannotwhatformalgrammarterminated
Problem
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:
My professor described the result as "any number of
But what if I picked the first rule? So, I start with
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#3542, answer score: 10
Revisions (0)
No revisions yet.