Set of Palindromes over Infinite Set does not form Formal Language
Jump to navigation
Jump to search
Example of Formal Language
The set of palindromes over an infinite set of symbols does not form a formal language.
Proof
According to the alternative definition, formal language consists of a finite set of symbols.
As the set of symbols specified here is infinite, this does not fit the criteria.
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.1$ Strings, Alphabets and Languages