0
$\begingroup$

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

Finite-state automaton

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

$\endgroup$
4
  • $\begingroup$ (The left-regular grammar in the text hyperlinked seems to accept words ending in bac, only.) $\endgroup$
    – greybeard
    Oct 1 '21 at 4:29
  • $\begingroup$ @greybeard I made a typo by writing abc, sorry (edit accepted). $\endgroup$
    – Amessihel
    Oct 1 '21 at 7:35
  • 2
    $\begingroup$ Regular grammars correspond to NFAs. $\endgroup$ Oct 1 '21 at 9:09
  • $\begingroup$ @YuvalFilmus, oh thanks, I believed they have to be deterministic. $\endgroup$
    – Amessihel
    Oct 1 '21 at 11:02
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for this detailed answer. I had studied language theory a long time ago, I forgot a lot... :) My basic mistake was to assume a regular language must be generated only by deterministic grammar and automata. Your answer provide a global view on this point. $\endgroup$
    – Amessihel
    Oct 5 '21 at 8:02
  • $\begingroup$ Just to be sure, could you please confirm if the automata in my question is correct? $\endgroup$
    – Amessihel
    Oct 5 '21 at 8:03
  • 1
    $\begingroup$ @Amessihel It won't match $bbac$ or $babac$. The $b$ transitions need to go to $U$, not $S$. $\endgroup$
    – rici
    Oct 5 '21 at 11:44
  • $\begingroup$ I've just fixed it, thank you! $\endgroup$
    – Amessihel
    Oct 15 '21 at 10:48

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.