More abstract language theory

The concatenation operation

Before we give some example languages we will note a useful string operation, the concatenation operation. This operation simply takes two ( possibly identical ) strings and provides a third by writing the first directly after the second.

We also note that, we will freely use lower case Greek characters (except ε) to denote strings of symbols. For the purposes of this tutorial, we exclude lower case Greek character from the symbols appearing in an alphabet.

Examples Languages

Σ={ 1 }
rule  α in L-ODD if an only if length(α) is odd 
L-ODD={1, 111, 11111, ... } 

Σ={ 1 }
rule  α in L-NULL-ODD if an only if length(α) is odd or α =  ε
L-NULL-ODD={ε, 1, 111, 11111, ... } 

Σ={ 1 }
rule  α in L-NULL-ODD if an only if length(α) is even or α =  ε
L-NULL-EVEN={ε, 11, 1111, 111111, ... } 

More operations concatenating and exponentiation

The result of concatenating two strings need not necessarily be a word in a Language even if both strings are words in that Language. For example:

both 1 and 111 are in L-NULL-ODD but
1111 ∉ L-NULL-ODD

Let α be a string then we define α raised to the power of 0 as ε

That is,
α° =  ε
Likewise,
 α¹ =  α
and
 α² =  αα

And, similarly for all mantissa α and any positive exponent n, α raised to the power of n is simply the n fold concatenation of α.

In addition,

In addition,  α¹ α²  =  α³ =  ααα

And this generalizes in the obvious fashion, for all positive exponents n and m, α raised to the power of n concatenated with α raised to the power of m is simply the (n+m) fold concatenation of α

More operations going backwards

The function reverse writes a string backwards.

The function reverse(α) for any string α is the string, the revered sequence of symbols of α

Example Language Palindromes

A Palindrome is a phrase spelled the same way forward as in reverse. So for example in English if we remove spaces and punctuation and translate to lower case "Madam, I'm Adam" becomes the palindrome
madamimadam
Similarly, "Never odd or even" is:
neveroddoreven
For a simple 2 symbol alphabet we define the language L-PALINDROMES.
Σ={ x,y }
rule  α in L-PALINDROMES if an only if reverse(α) = α
L-PALINDROMES={ε , x, y,xx,yy,xxx,xyx,yxy,xxxx, ... } 

Summary

  • Conatenation takes two strings and provides a third by writing the first directly after the second.
  • Concatenating two words need not necessarily be a word in a Language.
  • Exponentiation provides n fold concatenation.
  • A Palindrome is a phrase spelled the same way forward as in reverse.