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)
Posted: Jun 11 '12
Seen: 82 times
Last updated: Jun 11 '12
