Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAPTER 12 Languages, Automata, Grammars

12.1Introduction

This chapter discusses three topics,languages,automata, andgrammars. These three topics are closely

related to each other. Our languages will use the lettersa,b,...to code data rather than the digits 0 and 1 used

by some other texts.

12.2Alphabet, Words, Free Semigroup

Consider a nonempty setAof symbols.Awordorstringwon the setAis a finite sequence of its elements.

For example, supposeA={a, b, c}. Then the following sequences are words onA:

u=ababb and v=accbaaa

When discussing words onA, we frequently callAthealphabet, and its elements are calledletters. We will also

abbreviate our notation and writea^2 foraa,a^3 foraaa, and so on. Thus, for the above words,u=abab^2 and

v=ac^2 ba^3.

The empty sequence of letters, denoted byl(Greek letter lambda) or(Greek letter epsilon), or 1, is also

considered to be a word onA, called theempty word. The set of all words onAis denoted byA∗(read: “Astar”).

Thelengthof a wordu, written |u|orl(u), is the number of elements in its sequence of letters. For the

above wordsuandv, we havel(u)=5 andl(v)=7. Also,l(l)=0, wherelis the empty word.

Remark:Unless otherwise stated, the alphabetAwill be finite, the symbolsu, v, wwill be reserved for words

onA, and the elements ofAwill come from the lettersa, b, c.

Concatenation

Consider two wordsuandvon the alphabetA. Theconcatenationofuandv, writtenuv, is the word

obtained by writing down the letters ofufollowed by the letters ofv. For example, for the above wordsuandv,

we have

uv =ababbaccbaaa=abab^2 ac^2 ba^3

As with letters, for any wordu, we defineu^2 =uu, u^3 =uuu, and, in general,un+^1 =uun.

303

Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.