Confusion converting BNF to regular expression

Question

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> |
               <name>_<endtitle>

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

<endtitle> ::= ESQUIRE | OBE | CBE

<name> ::= <word> |
           <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.

context free regular expressions regular languages

PMar · Accepted Answer

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']

Confusion converting BNF to regular expression

One Answer

Add your own answers!

Ask a Question