context-free-grammarchomsky-normal-form

Making context free grammars simpler(prettier)


I'm working with CFG and every time I write up rules to a particular language, my CFG ends up disgusting. It ends up as one line:

S->tooooooo much stuff

I know that putting things into chomsky normal form will put it in the correct format and things will be prettier but I was wondering if there are any ideas to keep in mind for making these look less cluttered.

i.e., lang:

a^n b^m, where n >= m

My CFG (gross):

S -> Sa|Sab|Sba|aS|aSb|abS|bSa|baS|ε

Can anyone help me with my bad habits?


Solution

  • Do you really need to use CFG to describe this simple language? It would be much easier to just count the a's and b's.

    But assuming this is just an example...

    CFG's in real parsers usually split it up to one production per line, and group them in some reasonable way.

    S -> a b S
       | b a S
       | a S
       | a S b
       | b S a
       | ε