1
Three Basic Concepts
Languages

Grammars

Automata
2
Languages
Alphabet: a finte and nonempty set of symbols
 = {a, b}

String: finite sequence of symbols from 
w = abaaa

: empty string
*: the set of all strings on  (+ = *  {})
3
Languages
Language: a subset L of *


Sentence: a string in L
4
Languages
Example 1:
 = {a, b}
* = {, a, b, aa, ab, ba, aaa, ...}
L1 = {a, aa, aab} (finite language)
L2 = {anbn | n  0} = {, ab, aabb, ...}
5
Languages
Language concatenation:
L1L2 = {xy | xL1, yL2}
Ln = L L ... L (n times)
L0 = {}

6
Languages
Example 2:
L = {anbn | n  0}
L2 = {anbnambm | n  0, m  0}

7
Languages
Star-closure:
L* = L0  L1  L2 ...
Positive closure:
L+ = L1  L2 ...

8
Grammars
A grammar for a natural language tells us whether a particular sentence is well-formed or not.





 a | the
 boy | dog
 runs | walks

9
Grammars
Formal grammar:
G = (V, T, S, P)
V: finite set of variables
T: finite set of terminal symbols
SV: start variable
P: finite set of productions

10
Grammars
Productions:
x  y
x(VT)+ y(VT)*
w = uxv derives z = uyv
w  z
w1 * wn (w1  w2  ...  wn | w1 = wn)
w1 + wn
11
Grammars
Generated language:
G = (V, T, S, P)
L(G) = {wT* | S * w}
Derivation:
S  w1  w2  ...  wn  wL(G)
Sentential forms: S, w1, w2, ..., wn (containing variables)

12
Grammars
Example 3:
G = ({S}, {a, b}, S, P)
P: S  aSb
S  
S  aSb  aaSbb  aabb
aabb: sentence aaSbb: sentential form
13
Grammars
Example 3:
G = ({S}, {a, b}, S, P)
P: S  aSb
S  
L(G) = {anbn | n  0}

14
Grammars
Example 4:
G1 = ({A, S}, {a, b}, S, P1)
P1: S  aAb | 
A  aAb | 


15
Grammars
Example 4:
G1 = ({A, S}, {a, b}, S, P1)
P1: S  aAb | 
A  aAb | 
L(G1) = {anbn | n  0}
G and G1 are equivalent
16
Grammars
Example 5:
G2 = ({S}, {a, b}, S, P2)
P2: S  SS
S  
S  aSb
S  bSa

17
Grammars
Example 5:
G2 = ({S}, {a, b}, S, P2)
P2: S  SS
S  
S  aSb
S  bSa
L(G2) = {w | na(w) = nb(w)}
18
Automata
An abstract model of digital computer:
Control unit
Input file
Output
Storage
19
Automata
Input file: is divided into squares.
Input is a string over a given alphabet.
Each input square holds a symbol.
The symbols are read from left to right, one at a time.
The end of the input string can be detected.
20
Automata
Storage: consists of an unlimited number of cells.
Each cell can hold a symbol from an alphabet (which can be different from the input alphabet).
The contents of the storage cells can be read and changed.
21
Automata
Control unit: has a finite number of internal states.
Can be in any one of the internal states.
Can change state in some defined manner.
22
Automata
Transition function:
current state  input symbol  storage info  next state
Output may be produced
Info in the storage may be changed
Configuration: current state  input symbol  storage info
Move: current configuration  next configuration
23
Automata
General types of automata:
Accepter: yes/no output
Transducer: string of symbols as output
Deterministic: single move
Non-deterministic: multiple moves
24
Homework
Exercises: 4, 5, 6, 8, 9, 12, 15, 17 of Section 1.2 - Linz’s book.
Reading: Section 1.3 - Linz’s book.
Presentation: Section 2.4 - Linz’s book (procedures mark and reduce).