PadhaikoAll subjects

Alphabets, Languages & Operations on Languages

Theory of Computation (ENCT 203)

Open in the Padhaiko app

1.4 Alphabet, Strings, and Languages

Definition

Alphabet, String, Empty String, and String Length

Definition

Kleene Closure, Positive Closure, and Powers of an Alphabet

Let be an alphabet:

  1. Power of an Alphabet (): For any integer , is the set of all strings over of length exactly :
  1. Kleene Star / Kleene Closure (): The set of all strings over of length zero or more (including ):
  1. Positive Closure (): The set of all non-empty strings over (all strings of length one or more, excluding ):
Definition

String Operations: Concatenation, Prefix, Suffix, Substring, and Reversal

Let be strings over an alphabet :

Definition

Formal Language

A language over an alphabet is any set of strings chosen from :

Because a language is simply a subset of , it may be finite or infinite (and even the empty set and the singleton are valid languages, with since while ).

1.5 Operations on Languages: Union, Concatenation, Kleene Star

Definition

Union, Concatenation, and Kleene Star of Languages

Let be languages over an alphabet :

  1. Union (): The language consisting of all strings that belong to , or to , or to both:
  1. Concatenation ( or ): The language formed by concatenating each string in with each string in :
  1. Kleene Star (): The language of all strings obtained by concatenating zero or more strings chosen from :

where and for .

  1. Positive Closure (): The language of all strings obtained by concatenating one or more strings from :

Note that if and only if , and .

AspectKleene Closure (L*)Positive Closure (L+)
Definition
Number of Concatenated WordsZero or more strings from One or more strings from
Contains ?Always ( for every , including )Only if originally ()

Worked Out Examples

Example 1.24

1.24

For the string over , list all prefixes, suffixes, substrings, and find the reversal and length .

Length and reversal: The string has symbol occurrences, so . Writing its symbols in reverse order gives:

Prefixes, suffixes, and substrings:

  • Prefixes ( such that ): .
  • Suffixes ( such that ): .
  • Substrings ( such that ): .
Answer:

, , Prefixes , Suffixes , Substrings .

Example 1.25

1.25

Let and be two languages over . Compute:

  1. and

Computing the union : Collecting all strings in or :

Computing the concatenations and :

  • Pair each string of with each string of :
  • Pair each string of with each string of :

(Notice that language concatenation is not commutative: .)

Computing :

Answer:

, , , and .

Exercises

Exercise — Chapter 1 (Book Page 50)

Question 6

What are power of an alphabet and positive closure of an alphabet? [2081 Chaitra]

Power of an alphabet (): Let be an alphabet (a non-empty finite set of symbols). For any integer , the -th power of , denoted , is the set of all strings of length exactly composed of symbols from :

Formally defined by induction on :

  • Base: (where is the empty string of length ).
  • Inductive Step: for .

If , then the number of strings of length is .

  • Example: For ():

Positive closure of an alphabet (): The positive closure of an alphabet , denoted , is the set of all non-empty strings (strings of length or greater) that can be formed using symbols from :

Equivalently, it consists of the Kleene star excluding the empty string :

  • Example: For :

Note that , whereas .

Answer:
  • Power of an alphabet (): For an alphabet and integer , is the set of all strings over of length exactly . For , , , .
  • Positive closure of an alphabet (): is the set of all strings of length one or more over (all strings over except the empty string ). Thus .
Question 7

Define union, concatenation, and Kleene star operations on languages with an example of each.

Union operation on languages ():

  • Definition: The union of two languages and over an alphabet is the set of all strings that belong to , , or both:
  • Example: Let and .
  • Identity & Properties: , , and union is commutative ().

Concatenation operation on languages ():

  • Definition: The concatenation (product) of languages and is formed by taking every string in followed by every string in :
  • Example: Using and :

In contrast, . Concatenation is associative but generally non-commutative. Identity element: . Annihilator: .

Kleene Star / Kleene Closure operation ():

  • Definition: The Kleene star of a language , denoted , is the set of all strings formed by concatenating zero or more strings from :

where and for . By definition, for every language (including ).

  • Example: Let .

For , represents the set of all possible binary strings.

Answer:

For languages and :

  • Union: .
  • Concatenation: .
  • Kleene Star: is the set of all strings formed by concatenating zero or more strings from ; for , .

Past exam questions for Theory of Computation

← Induction, Diagonalization & Pigeonhole PrincipleFinite State Machines & DFA Design →