Languages

Slides have been modified by Shaukat Wasi

Courtesy: Costas Busch - LSU 1

Language: a set of strings

String: a sequence of symbols

from some alphabet

Example:
Strings: cat, dog, house
Language: {cat, dog, house}
Alphabet:   a, b, c,, z

Courtesy: Costas Busch - LSU 2

Languages are used to describe
computation problems:

PRIMES  {2,3,5,7,11,13,17,}

EVEN  {0,2,4,6,}

Alphabet:   {0,1,2,,9}

Courtesy: Costas Busch - LSU 3

Computation is translated to set membership

Example computation problem:

Is number x prime?

Equivalent set membership problem:

x  PRIMES  {2,3,5,7,11,13,17,}?

Courtesy: Costas Busch - LSU 4

 Alphabets and Strings
An alphabet is a set of symbols
Example Alphabet:   a, b
A string is a sequence of
symbols from the alphabet
String variables
a
u  ab
ab
Example Strings v  bbbaaa
abba w  abba
aaabbbaabab
Courtesy: Costas Busch - LSU 5
Decimal numbers alphabet   {0,1,2,,9}

102345 567463386

Binary numbers alphabet   {0,1}

100010001 101101111

Courtesy: Costas Busch - LSU 6

 Unary numbers alphabet   {1}

Unary number: 1 11 111 1111 11111

Decimal number: 1 2 3 4 5

Courtesy: Costas Busch - LSU 7

 String Operations

w  a1a2  an abba
v  b1b2 bm bbbaaa

Concatenation

wv  a1a2 anb1b2 bm abbabbbaaa

Courtesy: Costas Busch - LSU 8

w  a1a2  an ababaaabbb

Reverse

w  an  a2 a1
R
bbbaaababa

Courtesy: Costas Busch - LSU 9

 String Length
w  a1a2  an
Length: w n

Examples: abba  4
aa  2
a 1
Courtesy: Costas Busch - LSU 10
 Length of Concatenation

uv  u  v

Example: u  aab, u  3
v  abaab, v  5

uv  aababaab  8
uv  u  v  3  5  8
Courtesy: Costas Busch - LSU 11
 Empty String
A string with no letters is denoted:  or 
Acts as a neutral element
Observations:   0

w  w  w

abba  abba  abba  abba

Courtesy: Costas Busch - LSU 12
 Substring
Substring of string:
a subsequence of consecutive characters

String Substring
abbab ab
abbab abba
abbab b
abbab bbab
Courtesy: Costas Busch - LSU 13
 Prefix and Suffix
string abbab
Prefixes Suffixes
 abbab w  uv
a bbab
prefix
ab bab
suffix
abb ab
abba b
abbab 
Courtesy: Costas Busch - LSU 14
 Exponent Operation
w  ww
n

 
w
n

Example: abba  abbaabba

2

Definition: w 
0

abba    0

Courtesy: Costas Busch - LSU 15

 The * Operation
 *
: the set of all possible strings from
alphabet 

  a, b
   , a, b, aa, ab, ba, bb, aaa, aab,
*

Courtesy: Costas Busch - LSU 16

 The + Operation
 : the set of all possible strings from

alphabet  except 

  a, b
   , a, b, aa, ab, ba, bb, aaa, aab,
*

   
 *


  a, b, aa, ab, ba, bb, aaa, aab,
Courtesy: Costas Busch - LSU 17
 Languages
A language over alphabet 
is any subset of  *

Example:   a, b

   , a, b, aa, ab, ba, bb, aaa,

*

Languages: {}

a, aa, aab
{ , abba, baba, aa, ab, aaaaaa}
Courtesy: Costas Busch - LSU 18
 More Language Examples

Alphabet   {a, b}
An infinite language L  {a b : n  0} n n

 bbabb L
ab abb  L
L
aabb
aaaaabbbbb
Courtesy: Costas Busch - LSU 19
 Prime numbers
Rule: Numbers divisible by 1 and itself

Alphabet   {0,1,2,,9}
Language:

PRIMES  {x : x   and x is prime}

*

PRIMES  {2,3,5,7,11,13,17,}

Courtesy: Costas Busch - LSU 20

 Even and odd numbers

Alphabet   {0,1,2,,9}
Languages:
EVEN  {x : x   and x is even}
*

EVEN  {0,2,4,6,}

ODD  {x : x   and x is odd}

*

ODD  {1,3,5,7,}
Courtesy: Costas Busch - LSU 21
 Addition (of unary numbers)

Alphabet:   {1,, }
Language:
ADDITION  {x  y  z : x  1 , y  1 , z  1 , n m k

n  m  k , n  1, m  1}
11  111  11111 ADDITION
111111  111 ADDITION
ADDITION  {1  1  11,1  11  111,11  1  111,11  11  1111, ...}
Courtesy: Costas Busch - LSU 22
 Squares (of unary numbers)

Alphabet:   {1, # }
Language:
SQUARES  {x#y : x  1 ,y  1 , m  n }n m 2

11#1111 SQUARES
111#1111 SQUARES
SQUARES  {1#1,11#1111,111#111111111, ...}
Courtesy: Costas Busch - LSU 23
 Two special languages

Language with
Empty language empty string
{ } or  { }
Size of a language (number of elements):
| {} | 0
|  | 1
| a, aa, ab| 3
| { , aa, bb, abba, baba} | 5
Courtesy: Costas Busch - LSU 24
 Note that:

Sets   { }  {}

Set size {}    0

Set size {}  1

String length  0
Courtesy: Costas Busch - LSU 25
 Operations on Languages
The usual set operations:

a, ab, aaaa bb, ab  {a, ab, bb, aaaa} union
a, ab, aaaa bb, ab  {ab} intersecti on
a, ab, aaaa bb, ab  a, aaaa difference

Complement: L  L *

a, ba   , b, aa, ab, bb, aaa,

Courtesy: Costas Busch - LSU 26
 Reverse

Definition: L  {w : w  L}
R R

Examples: ab, aab, baba  ba, baa, abab

R

L  {a b : n  0}
n n

L  {b a : n  0}
R n n

Courtesy: Costas Busch - LSU 27

 Concatenation

Definition: L1L2  xy : x  L1, y  L2 

Example: a, ab, bab, aa

 ab, aaa, abb, abaa, bab, baaa

Courtesy: Costas Busch - LSU 28

 Another Operation
Definition: L 
n

LL L
n

a, b  a, ba, ba, b 

3

aaa, aab, aba, abb, baa, bab, bba, bbb

Special case: L0  

a, bba, aaa   0

Courtesy: Costas Busch - LSU 29

Example

L  {a b : n  0}
n n

L  {a b a b : n, m  0}
2 n n m m

2
aabbaaabbb L
?????? L 2

Courtesy: Costas Busch - LSU 30

 Star-Closure (Kleene *)
All strings that can be constructed from L

Definition: L  L  L  L 
* 0 1 2

Example:
 , L
0

a, bb,  L1
 
a, bb*    L2
 aa , abb, bba , bbbb, 
aaa, aabb, abba, abbbb, L3

Courtesy: Costas Busch - LSU 31

 Positive Closure


Definition: L  L  L  L 
1 2 3

Note that: L  L  L
* 0 

a, bb, L
1

   2
a, bb  aa, abb, bba, bbbb, L
aaa, aabb, abba, abbbb, L3
 
Courtesy: Costas Busch - LSU 32
CLASS ACTIVITY#01

Courtesy: Costas Busch - LSU 33