How to convert this regular grammar into a finite state automaton?

Question

In a French course (p. 13) there is a language of words of {a,b,c} containing at least one occurrence of the string bac.

The course provide also among other things this right-regular grammar below:

T = { a,b,c }
N = { S,U,V,W }
R = { S → aS | bS | cS | bU
      U → aV
      V → cW | c
      W → aW | bW | cW | a | b | c }

What bugs me is the first rule: b can be followed both by S or U but it sounds like a non-deterministic grammar. I tried to build a finite-state automaton from this language, starting for the description phrased at the beginning to see if I could end with something looking like the grammar. It is reproduced below (fixed, thanks to @rici).

I don't think it is, except if I remove bS in the first rule. Where am I wrong?

Answer 1

The language of a right-regular grammar is certainly deterministic, because the grammar can be written as an NFA and any NFA can be mechanically transformed into an equivalent DFA using the subset construction.

However, the grammar may well be ambiguous (i.e. capable of producing multiple parse trees for the same input.) That's the case for the grammar you show, which might transition to $U$ after any instance of $bac$, not just the first one.

Since the NFA can be transformed into a DFA and the DFA back into a right regular grammar, we can conclude that the language is deterministic, in the sense that a deterministic grammar exists. (And a deterministic grammar is clearly not ambiguous.) But that deterministic grammar does not use the same grammatical categories (non-terminals), so it won't produce the intended parse tree (if there was such an intention).

This distinction probably makes little difference at this point in your studies, but it may be useful to hold it in mind. Regular expressions are typically used when the internal structure of the input is unimportant, so that a machine which simply returns a yes/no indication is of practical value and the determinism of the machine's internal workings is irrelevant.

Parsing, on the other hand, means analyzing the input into its component parts (the similarity of the two words is not a coincidence). So when you later want to build parsers, you'll want a machine which transforms a correct input into a parse tree (or some other similar representation), and the question of determinism becomes more interesting.

In any case, you need always to clearly distinguish between a characteristic of a grammar and a characteristic of a language, even if the same word is used for both.

Typically we say that a language $L$ has property $P$ if and only if there exists some grammar $G$ which has property $P$ and which generates (or recognises) language $L$. That's a notational shortcut which lets us extend characteristics of grammars onto languages, but it must not be read to imply that every grammar for the language has the indicated property. This is a frequent cause of confusion.