Maybe you get a better understanding if you remember the automata generating these languages. Regular languages are generated by regular automata. They have only have a finit knowledge of the past (their compute memory has limits) so everytime you have a language with suffixes depending on prefixes (palindrome language) this can not be done with … Read more
Trying to find the complexity of this problem lead me to this paper. The formal definition of the problem can be found within: this is generally called the inclusion problem The inclusion problem for R, is to test for two given expressions r, r′ ∈ R, whether r ⊆ r′. That paper has some great … Read more
In the context of computer science, a word is the concatenation of symbols. The used symbols are called the alphabet. For example, some words formed out of the alphabet {0,1,2,3,4,5,6,7,8,9} would be 1, 2, 12, 543, 1000, and 002. A language is then a subset of all possible words. For example, we might want to … Read more
Regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. Hence you can see that regular grammar is a subset of context-free grammar. So for a palindrome for instance, is of the form, S->ABA A->something B->something You can clearly see that palindromes cannot be expressed … Read more