Defining Languages: Patterns in Sets of Strings
Ganesh Lalitha Gopalakrishnan · 2019
This chapter begins with how strings are formed from symbols over an alphabet, and how languages (sets of strings) can be defined and operated upon. Four notions are basic to the study of computations: Symbol, Alphabet, String, and Language. Symbols are taken to be primitives in each context. Two strings are concatenated to obtain a new string. Concatenation is expressed through juxtaposition. The chapter discusses what the Zero is and what the One is for various situations (i. e., different algebraic systems). This will serve as a powerful memory aid for many language-theoretic rules that are otherwise difficult to intuitively understand. The chapter defines the exponentiation of a language, which simply means “repeated concatenation” of a language. It discusses Python encoding of language exponentiation, and union and intersection of languages.