CS3518 Formal Languages and Computability: Week One Summary

Formal Languages

Terminology

Symbol: basic unit
Alphabet: finite set of symbols
String over alphabet T: finite sequence of symbols from T
Empty string: string with no symbols, lambda, λ.

Definitions

Substrings: Strings are prefix's and suffix's of themselves, unless denoted 'proper' eg 'proper prefix'.
T*: If T is an alphabet then T* is the set of all strings over T.
T+: T* excluding λ.
aⁿ: for example: sa⁴ = sasasasa

Languages

Language: A language over an alphabet T is a a set of strings over T. It is a subset of T*

Let A and B be languages over T

A+B: union of A and B
A ∩ B: intersection of A and B
A`: the complement of A; all strings in T* excluding A
AB: concatenation of A and B; all strings uv where u ∈ A and v ∈ B

Ordering

Dictionary alphabetical ordering.
Lexical shortest string first (starting with λ)

Specifying Languages

L₁ = { xⁿ : n = 1, 2, 3, ... }
- Not precise.

Languages and Machines

Languages represent problems

Question / answer:
- Yes/no decision.
- Functional (is 17⁹⁷⁴⁸ prime?)
Problem / solution:
- Next best move in chess game
Task / achievement:
- How to get out of a maze?
- How to drive on a roundabout?

A class of languages is a useful abstraction for a class of problems.

CS3518 Formal Languages and Computability: Week Two Summary

Finite State Automata (FSA)

Finite State Automaton: an abstract model of a simple machine.
- Finite number of states.
  - Receives symbols as input
  - Symbols + present state => new state.
Finishing state: when the input ends the machine has accepted the input.

FSA: Formal Definition

A Finite State Automaton (FSA) is a 5-tuple (Q, I, F, T, E) where:
    Q = states         = a finite set;
    I = initial states = a nonempty subset of Q;
    F = final states   = a subset of Q;
    T = an alphabet;
    E = edges          = a subset of Q × (T + λ ) × Q.

Example: Formal definition of A₁

TODO: put the graph image here.

Q = {1, 2, 3, 4 }
I = {1}
F = {4}
T = {a, b}
E = { (1,a,2), (1,b,4), (2,a,3), (20,b,4), (3,a,3), (3,b,3), (4,a,2), (4,b,4) }

Acception

Edge: (x, a, y)
Start state: x
End state: y
Path: sequence of edges such that the end state of one is the start state of another.

Example: path p₁ = (2,b,4), (4,a,2), (2,a,3)

Successful if:
- Start state of the first edge is an initial state ( ∈ I ).
- End state of the last edge is a final state ( ∈ F ).

Example: path p₂ = (1,b,4), (4,a,2), (2,b,4), (4,b,4)

Label: of a path is the sequence of edge labels.

A string is accepted by a FSA if it is the label of a successful path

Example: babb = label(p₂) is accepted by A(₁).

Let A be a FSA.

Language accepted by A: the set of strings accepted by A, L(A).

Determinism

DFSA: deterministic FSA.
NDFSA: non-deterministic FSA.

We would like to recognise languages by traversing the graph, however an FSA as defined above can be nondeterministic. How?

2+ edges from a state with the same label.
Edges can be labelled with λ

2+ initial states.

 A FSA is deterministic if:
   (i)   there are no λ-labelled edges;
   (ii)  for any pair of state and symbol (q,t), there is at most one edge (q,t,p);
   (iii) there is only one initial state.

Transition Functions

δ : (x,t) ‖ { y: ∃ edge (x,t,y) in A }

If A = (Q,I,F,T,E), then the transition matrix for A is a matrix with one row for each state in Q, one column for each symbol in T, such that the entry in row x and column t is δ(x,t).

Example using FSA A₁

State	symbol a	symbol b
→ 1	{2}	{4}
2	{3}	{4}
3	{3}	{4}
← 4	{2}	{4}

###Recognition Algorithm
Problem: Given a DFSA, A={Q, I, F, T, E), and a string w, determine whether w ∈ L(A)

let q be the current state and t be the current input symbol.

Since A is deterministic, δ(q,t) will always be a singleton set (or is undefined). If it is undefined, denote it by ⊥ (∉ Q).

Procedural solution

Add symbol # to end of w.
q := initial state
t := first symbol of w#
while (t ≠ # and q ≠ ⊥)
begin
    q := δ(q,t)
    t := next symbol of w#
end
return ((t == #) & (q ∈ F))

Equivalence of DFSA's and NDFSA's

TODO

Minimum Size of FSA's