# A Formal Grammar: defining English counting numbers?

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"

• "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). – rici Feb 15 at 17:08
• 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. – Nick Feb 17 at 20:57
• @rici I updated the grammar, appreciate any feedback – Nick Feb 17 at 22:02
• 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). – rici Feb 17 at 23:12
• 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? – Nick Feb 18 at 0:36