I have a Computer Science A-Level exam tomorrow and I've been trying to get this question answered by my teacher but she's not been too helpful so asking here instead.

In an exam question, I have the following BNF grammar, where _ denotes a space.

<fullname> ::= <title>_<name>_<endtitle> |
               <name> |
               <title>_<name> |

<title> ::= MRS | MS | ... | SIR

<endtitle> ::= ESQUIRE | OBE | CBE

<name> ::= <word> |

<word> ::= <char><word>

<char> ::= A | B | ... | Z

The mark scheme says that the first rule, fullname, can be represented with a regular expression. But I'm not really sure how you could represent it with a regular expression when it's made up of other rules that can't be represented by regular expressions themselves e.g. name which is recursive. Also I thought regular expressions were made up of just letters and symbols e.g. a*b? . Forgive me if I don't seem too knowledgable on this because the resources we have for the A-Level are pretty awful.


1 Answer 1


There are two ways of interpreting 'the first rule can be represented with a regular expression'; you should review this 'mark scheme' to determine which applies. One possibility is that the first rule is being treated as defining a language over its own terminals and non-terminals, without ever expanding the non-terminals. I.e, think of treating the tokens 'title', 'name', and 'endtitle' as single characters of the 'language' of 'fullname' (along with the space-char). Then it is easy to see that that is a regular language - there are only four strings in it!

The other possibility is what you assumed, i.e that non-terminals are to be expanded. In this case your observation that 'name' is recursive is misplaced. The issue is not whether the set of productions for that non-terminal is regular, the issue is whether the set of strings generated from that non-terminal is regular. For 'name' the answer is yes: The set of strings generated from 'name' is seen, with a little thought, to be simply a sequence of one or more 'word'-s separated by spaces, for which a regular expression is easy to construct [given a regular expression for 'word', of course]. So yes, in this case 'fullname' generates a regular language.

[P.S. Note: Your 'word' is missing a production for a single 'char']

  • $\begingroup$ Ok so a regular expression defines a set, either a set of productions or set of strings? And I think the mark scheme indicates they use the former, as it says name and word cannot be defined with a regular expression. $\endgroup$
    – HazNut
    Jun 15, 2017 at 20:47
  • $\begingroup$ The idea that this discussion wants is the working set. $\endgroup$
    – Thumbnail
    Jun 16, 2017 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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