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

Related Content