الرئيسية  |  القسم الاكاديمي  |  القسم الاعلامي  |  اللوحة الافتراضية  |  القسم الاخباري  |  نظام المحاضرات  |  قسم المعلومات

انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

هياكل متقطعة II +languages , Automata

الكلية كلية تكنولوجيا المعلومات     القسم قسم البرامجيات     المرحلة 1
أستاذ المادة سرى زكي ناجي علوان       4/10/2011 9:44:43 AM

Languages,  Automata

 

 

 

 

 

 1   INTRODUCTION

 

 

This chapter discusses three topics, languages, automata, and grammars.  These three topics are closely related to each other. Our languages will use the letters a, b, ... to code data rather than the digits 0 and 1 used by some other texts.

 

 

 

 2   ALPHABET, WORDS, FREE SEMIGROUP

 

 

Consider a nonempty set A of symbols. A word or string w on the set A is a ?nite sequence of its elements. For example, suppose A = {a, b, c}. Then the following sequences are words on A:

 

u = ababb    and    v = accbaaa

 

 

When discussing words on A, we frequently call A the alphabet, and its elements are called letters. We will also abbreviate our notation and write a2  for aa, a3  for aaa, and so on. Thus, for the above words, u = abab2  and v = ac2 ba3 .

 

The empty sequence of letters, denoted by l (Greek letter lambda) or    (Greek letter epsilon), or 1, is also considered to be a word on A, called the empty word. The set of all words on A is denoted by A? (read: “A star”).

 

The length of a word u, written  |u| or l(u), is the number of elements in its sequence of letters.  For the above words u and v, we have l(u) = 5 and l(v) = 7. Also, l(l) = 0, where l is the empty word.

 

 

Remark: Unless otherwise stated, the alphabet A will be ?nite, the symbols u, v, w will be reserved for words on A, and the elements of A will come from the letters a, b, c.

 

 

 

Concatenation

 

 

Consider two words u and v on the alphabet A.  The concatenation of u and v, written uv, is the word obtained by writing down the letters of u followed by the letters of v. For example, for the above words u and v, we have

 

uv  = ababbaccbaaa = abab2 ac2 ba3

 

As with letters, for any word u, we de?ne u2  = uu, u3  = uuu, and, in general, un+1 = uun .

 

 

 

.

 

 

 

Clearly, for any words u, v, w, the words (uv)w and u(vw) are identical, they simply consist of the letters of u, v, w written down one after the other. Also, adjoining the empty word before or after a word u does not change the word u. That is:

 

 

Theorem  1:  The concatenation operation for words on an alphabet A is associative. The empty word l is an identity element for the operation.

 

(Generally speaking, the operation is not commutative, e.g., uv = vu for the above words u and v.)

 

 

 

Subwords, Initial Segments

 

 

Consider any word u = a1 a2 ... an  on an alphabet A. Any sequence w = aj aj +1 ... ak  is called a subword of u. In particular, the subword w = a1 a2 ... ak  beginning with the ?rst letter of u, is called an initial segment of u. In other words, w is a subword of u if u = v1 wv2  and w is an initial segment of u if u = wv. Observe that l and u are both subwords of uv since u = lu.

 

Consider the word u = abca. The subwords and initial segments of u follow:

 

 

(1)  Subwords: l, a, b, c, ab, bc, ca, abc, bca, abca = u

 

(2)  Initial segments: l, a, ab, abc, abca = u.

 

 

Observe that the subword w = a appears in two places in u. The word ac is not a subword of u even though all its letters belong to u.

 

 

 

Free Semigroup, Free Monoid

 

 

Let F denote the set of all nonempty words from an alphabet A with the operation of concatenation. As noted above, the operation is associative. Thus F is a semigroup; it is called the free semigroup over A or the free semigroup generated by A.  One can easily show that F satis?es the right and left cancellation laws. However, F is not commutative when A has more than one element. We will write FA  for the free semigroup over A when we want to specify the set A.

 

Now let M = A* be the set of all words from A including the empty word l. Since l is an identity element

 

for the operation of concatenation, M is a monoid, called the free monoid over A.

 

 

 


المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .