1.5 RELATIONS


1.4 REGULAR EXPRESSION NOTATION/FINITE AUTOMATA DEFINITIONS

String

A string is a finite sequence of symbols. We use a letter, such as w , to denote a string. If w is the string, then the length of string is denoted as w , and it is a count of number of symbols of w . For example, if w = xyz , w = 3. If w = 0, then the string is called an "empty" string, and we use ˆˆ to denote the empty string.

Prefix

A string's prefix is the string formed by taking any number of leading symbols of string. For example, if w = abc , then ˆˆ , a , ab , and abc are the prefixes of w . Any prefix of a string other than the string itself is called a "proper" prefix of the string.

Suffix

A string's suffix is formed by taking any number of trailing symbols of a string. For example, if w = abc , then ˆˆ , c , bc , and abc are the suffixes of the w . Similar to prefixes, any suffix of a string other than the string itself is called a "proper" suffix of the string.

Concatenation

If w 1 and w 2 are two strings, then the concatenation of w 1 and w 2 is denoted as w 1 . w 2 ”simply, a string obtained by writing w 1 followed by w 2 without any space in between (i.e., a juxtaposition of w 1 and w 2 ). For example, if w 1 = xyz , and w 2 = abc , then w 1 . w 2 = xyzabc . If w is a string, then w . ˆˆ = w , and ˆˆ . w = w . Therefore, we conclude that ˆˆ (empty string) is a concatenation identity.

Alphabet

An alphabet is a finite set of symbols denoted by the symbol & pound ; .

Language

A language is a set of strings formed by using the symbols belonging to some previously chosen alphabet. For example, if = { 0, 1 }, then one of the languages that can be defined over this will be L = { ˆˆ , 0, 00, 000, 1, 11, 111, }.

Set

A set is a collection of objects. It is denoted by the following methods :

  1. We can enumerate the members by placing them within curly brackets ({ }). For example, the set A is defined by: A = { 0, 1, 2 }.

  2. We can use a predetermined notation in which the set is denoted as: A = { x P ( x ) }. This means that A is a set of all those elements x for which the predicate P ( x ) is true. For example, a set of all integers divisible by three will be denoted as: A = { x x is an integer and x mod 3 = 0}.

Set Operations

  • Union: If A and B are the two sets, then the union of A and B is denoted as: A ˆ B = { x x in A or x is in B }.

  • Intersection: If A and B are the two sets, then the intersection of A and B is denoted as: A ˆ B = { x x is in A and x is in B }.

  • Set difference: If A and B are the two sets, then the difference of A and B is denoted as: A ˆ’ B = { x x is in A but not in B }.

  • Cartesian product: If A and B are the two sets, then the Cartesian product of A and B is denoted as: A B = { ( a , b ) a is in A and b is in B }.

  • Power set: If A is the set, then the power set of A is denoted as : 2 A = P P is a subset of A } (i.e., the set contains of all possible subsets of A .) For example:

  • Concatenation: If A and B are the two sets, then the concatenation of A and B is denoted as: AB = { ab a is in A and b is in B }. For example, if A = { 0, 1 } and B = { 1, 2 }, then AB = { 01, 02, 11, 12 }.

  • Closure: If A is a set, then closure of A is denoted as: A * = A ˆ A 1 ˆ A 2 ˆ ˆ A ˆ , where A i is the i th power of set A , defined as A i = A.A.A i times.

    • (i.e., the set of all possible combination of members of A of length 0)

    • (i.e., the set of all possible combination of members of A of length 1)

    • (i.e., the set of all possible combinations of members of A of length 2)

Therefore A * is the set of all possible combinations of the members of A . For example, if = { 0,1), then * will be the set of all possible combinations of zeros and ones, which is one of the languages defined over .




Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net