Alphabets, Languages & Operations on Languages
Open in the Padhaiko app1.4 Alphabet, Strings, and Languages
Alphabet, String, Empty String, and String Length
- Alphabet (): A finite, non-empty set of symbols (characters).
- Examples: The binary alphabet , the lowercase alphabet , or the ASCII character set.
- String (or Word): A finite sequence of symbols juxtaposed from a given alphabet , usually denoted by .
- Examples: are strings over , and are strings over .
- Empty String (, , or ): The unique string with zero occurrences of symbols.
- Length of a String (): The number of symbol occurrences (positions) in the string .
- Examples: For , ; for the empty string, .
Kleene Closure, Positive Closure, and Powers of an Alphabet
Let be an alphabet:
- Power of an Alphabet (): For any integer , is the set of all strings over of length exactly :
- For :
- In general, if , then .
- Kleene Star / Kleene Closure (): The set of all strings over of length zero or more (including ):
- For : .
- Similarly, and .
- Positive Closure (): The set of all non-empty strings over (all strings of length one or more, excluding ):
- For : .
- Similarly, and .
- Relationship between and :
String Operations: Concatenation, Prefix, Suffix, Substring, and Reversal
Let be strings over an alphabet :
- Concatenation of Strings ( or ): Combining two strings and by appending the symbols of immediately after the symbols of .
- Example: If and , then , and .
- The empty string is the identity for concatenation: .
- Prefix of a String: A string is a prefix of if for some string . (If and , is a proper prefix.)
- Suffix of a String: A string is a suffix of if for some string . (If and , is a proper suffix.)
- Substring of a String: A string is a substring of if for some strings (where and may be ). Every string has and itself as substrings.
- Reversal of a String (): The string obtained by writing the symbols of in reverse order.
- Example: If , then . Inductively, and for .
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 ).
- Example 1: The language of strings over with an odd number of 's:
- Example 2: The language of binary strings with an even number of zeros:
1.5 Operations on Languages: Union, Concatenation, Kleene Star
Union, Concatenation, and Kleene Star of Languages
Let be languages over an alphabet :
- Union (): The language consisting of all strings that belong to , or to , or to both:
- Book Example: If and , then
- Concatenation ( or ): The language formed by concatenating each string in with each string in :
- Book Example: If and , then
- Kleene Star (): The language of all strings obtained by concatenating zero or more strings chosen from :
where and for .
- Important Note: always contains the empty string (even when , since ).
- Book Example: If , then
- Positive Closure (): The language of all strings obtained by concatenating one or more strings from :
Note that if and only if , and .
| Aspect | Kleene Closure (L*) | Positive Closure (L+) |
|---|---|---|
| Definition | ||
| Number of Concatenated Words | Zero or more strings from | One or more strings from |
| Contains ? | Always ( for every , including ) | Only if originally () |
Worked Out Examples
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 ): .
, , Prefixes , Suffixes , Substrings .
1.25
Let and be two languages over . Compute:
- 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 :
, , , and .
Exercises
Exercise — Chapter 1 (Book Page 50)
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 .
- 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 .
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.
For languages and :
- Union: .
- Concatenation: .
- Kleene Star: is the set of all strings formed by concatenating zero or more strings from ; for , .