Subscribe to the weekly news from TrueShelf

## Non-double words form a context-free language

Define double words whose first and second half is the same, e.g. baba or aaaa but not abba, bab or bababa. Prove that over a finite alphabet the language of non-double words is context-free. (Context-free has a very simple definition, see http://en.wikipedia.org/wiki/Context-free_language)