I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am not entirely sure thats the case. Is this a context-free or context-sensitive grammar? If context-free, do my production rules look ok?

For example:

"one hundred twenty two" $\in \Sigma^*$ which has the semantic meaning $b^2+2b^1+2b^0$

"one thousand two hundred thirty three" $\in \Sigma^*$, $b^3+2b^2+3b^1+3b^0$

I understand context-free production rules are $N \rightarrow \alpha$ and context-sensitive $\alpha N \beta \rightarrow \alpha \gamma \beta$, where $N$ is a non-terminal and $\alpha,\gamma$ are terminals or non-terminals.

I considered CFG production rules in Backus Naur Form as follows, but am unsure if it's correct:

<S> := "zero" | <b3> | <thou> | <mill> | <bill> | ""
<num99> := <ones> | <teens> | <tens> | <tens> <ones>
<num99opt> := <num99> | ""
<b3> := <ones> "hundred" <num99opt> | <num99> 
<b3op> := <b3> | ""
<thou> := <b3> "thousand" <b3op>
<thouop> := <thou> | <b3op>
<mill> := <b3> "million" <thouop>
<millop>:= <mill> | <thouop>
<bill> := <b3> "billion" <millop>
<tens> := "twenty" | "thirty" | ... | "ninety" 
<teens> := "ten" | "eleven" | ... | "nineteen"
<ones> := "one" | "two" | ... | "nine" 
  • 2
    $\begingroup$ "I understand context-free production rules are $N→α$ and context-sensitive $αNβ→αγβ$." Ok, in that case why do you have any doubt about whether your grammar is context-free? Or do you mean that you are not sure that the language is context-free, which is a different question (but the answer is that it is). $\endgroup$ – rici Feb 15 at 17:08
  • $\begingroup$ I note the supplied grammar is CFG, however am unsure it is correct to generate the grammar described. Given your comment, it appears this is a CFG. $\endgroup$ – Nick Feb 17 at 20:57
  • $\begingroup$ @rici I updated the grammar, appreciate any feedback $\endgroup$ – Nick Feb 17 at 22:02
  • $\begingroup$ That grammar looks fine (and obviously could be extended for larger numbers). Note that there are only a finite number of derivable phrases. (It's a large number, but it's still finite.) All finite languages are regular (and therefore context free, because regular languages are a strict subset of context free languages). $\endgroup$ – rici Feb 17 at 23:12
  • $\begingroup$ Thanks. I suspect the grammar produces finite derivations because of the largest prefix, i.e. "million", "billion", "trillion". I'm confused why it is regular. I saw that regular grammars are defined such that the production rules are in the form $A \rightarrow aB$ or $A \rightarrow a$, where $A,B \in N$ and $a \in \Sigma^*$ and where only a single non-terminal is allowed on the RHS. The above grammar has multiple non-terminals on the RHS, so differs from the definition of a regular grammar. Am I missing something? $\endgroup$ – Nick Feb 18 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.