Computing

210 ◾ Computing

In the denition given above, R • S is the concatenation of languages R

and S, i.e., the set of strings formed by choosing any (prex) string from

the set R and following it with any (sux) string from S. e * operation

in R*, sometimes called the Kleene star, is the set of strings formed by

any number of concatenations of strings from R, including the null length

string ε. For example, (0 + 1)* denotes the set of all possible binary strings,

whereas (0 + 1)(00 + 01 + 10 + 11)*1 denotes the language/set of all even

length strings representing odd numbers.

e computational abilities of the FAs are severely limited. ere are

many important sets that cannot be recognized by any FA. at is, most

nontrivial problems cannot be ...