How to define floats with same number of digits with context-free grammar

Question

I can't figure out on my own how do this exercise. I need to define context-free grammar that is able to write positive floats with same number of digits on left and right side of comma. Something like that L = { {0..9}^k,{0..9}^k | k is positive integeer} I would appreciate any kind of help. Sorry for my English, I haven't used it recently.

Answer 1

Wikipedia has quite a useful example of the type of grammar your're looking for. The key is to use recursion to build up from the first matching string to all possible matching strings.

The first matching string would be

L = {0..9},{0..9}

This would match 0,0 1,0 2,1 etc...

Next you recurse this definition to increase the number of digits on both sides by one

L = {0..9}L{0..9}

Which on the first iteration would match 10,01 21,03 12,14 and then on subsequent iterations matches larger and larger strings upto Aleph-0 (the countable infinity)