CSI3104 Introduction to Formal Languages Lecture Notes


CSI3104 Introduction to Formal Languages Lecture Notes Amy Felty Winter 2017 I. Theory of Automata II. Theory of Context-Free Languages III. Theory of Turing Machines

Chapter 1: Background and Introduction ● Theory of computers Study of mathematical models ◆ Abstract ◆ Simplify ◆ Codify (relate in a meaningful way to the physical world)

● Computability


● Basic questions  What do theoretical models of a computer look like?  What can we compute and what can’t we compute with today’s computers as well as computers of the future?  Why? ● We study some precise answers.  In particular, we formulate precise questions with mathematical statements and rigorous proofs.


History ● ● ● ●

Cantor (1845-1918) theory of sets Hilbert (1862-1943) methodology for finding proofs Gödel (1906-1978) Incompleteness theorem Church, Kleene, Post, Markov, von Neumann, Turing Which statements have proofs? building blocks of mathematical algorithms ● Turing (1912-1954) Universal machine and its limitations ● McCulloch, Pitts Neural nets (similar but with different limitations) ● Chomsky mathematical models for the description of languages 4

p. 434


Language Defined by

Corresponding Accepting Machine

Language NondeterClosed minism= Determinism Under

What Can Be Decided?

Examples of Applications

Regular expression

Finite automaton, transition graph


Union, product, Kleene star, intersection, complement

Equivalence, emptiness, finiteness, membership

Text editors, sequential circuits, verification

Context-free grammar

Pushdown automaton


Union, product, Kleene star

Emptiness, finiteness, membership

Parsing, compilers

Type 0 grammar

Turing machine, Post machine, Pushdown automaton


Union, product, Kleene star

Not much





Chapter 2: Languages ● Mathematical models of computers  Analysis of the input language ◆ Study their limitations

● Definitions  alphabet – a finite set of symbols, denoted Σ  letter – an element of an alphabet Σ  word – a finite sequence of letters from the alphabet Σ  Λ (empty string) – a word without letters  language – a set of words formed from the alphabet Σ


Two Examples English-Words




Γ=words in dictionary + space + punctuation marks








all the words in the dictionary

all English sentences


2 ways to define languages  a list of all the words  a set of rules (grammar) The alphabet is always finite. The set of words can be infinite. Syntax, not semantics What kind of rules are permitted? It must be possible in finite time to determine if a word is in a language or not. (algorithm) 8

● Example L1:


L1={x, xx, xxx, xxxx,…} or L1={xn | n=1, 2, 3,…}

● Definition: concatenation – two words written down side by side. A new word is formed. a=xx b=xxx ab=xxxxx factor – one of the two words in a concatenation xx|xxx ● Example L2: Σ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L2={words that do not start with the letter 0} 9

● Definition: length – number of letters in a word length(xxxxx) = 5 length(1025)=4 length(Λ)=0 reverse reverse(xxx)=xxx reverse(157)=751 ● Example PALINDROME: Σ={a, b} PALINDROME:={Λ and x|reverse(x) = x} 10

Kleene Closure ● Definition: closure of an alphabet Σ, Kleene star Given an alphabet Σ, the closure of Σ (or Kleene star), denoted Σ*, is the language containing all words made up of finite sequences of letters from Σ, including the empty string Λ. ● Examples:  Σ = {x}  Σ = {0, 1}  Σ = {a, b, c}

Σ* = {Λ, x, xx, xxx, …} Σ* = {Λ, 0, 1, 00, 01, 10, 11, 000, 001, …} Σ* = ?


● Definition: closure or Kleene star of a set of words (or a language) Let S be a set of words. S* is the language formed by concatenating words from S, including the empty string Λ. ● Examples:  S = {a, ab} S* = {Λ, a, aa, ab, aaa, aab, aba, aaaa, …} abaaababa ∈ S* ab|a|a|ab|ab|a factors S* = {Λ plus all sequences of a’s and b’s except those that start with b and those that contain a double b} Is the factoring always unique? 12

A Factoring that is not Unique S = {xx, xxx} xxxxxxx ∈ S* xx|xx|xxx



S* = {Λ and all sequences of more than one x}


● Example:


Σ* = {Λ}

● The Kleene closure of an alphabet Σ always produces an infinite language unless Σ is empty. ● Example: S = {a, b, ab} S* = T* ab|a|a|ab|ab|a a|b|a|a|a|b|a|b|a

T = {a, b, bb}

● The Kleene closure of a language S always produces an infinite language unless S = φ or S = {Λ}. In this case, S* = {Λ}. 14

Positive Closure ● Definition: S+, Σ+ The language with all concatenations that contain at least 1 word from S 1 letter from Σ (S* possibly without Λ) If Λ is a member of S, S* = S+. ● Examples:  Σ = {x} Σ+ = {x, xx, xxx, …}  S = {aa, bbb, Λ} S+ = {aa, bbb, Λ, aaaa, aabbb, …} (N.B. aΛ = a) 15

● Theorem 1: For any set of words S, we have S**=S*. ● Definitions: equality of sets S = T: S ⊂ T and T ⊂ S subsets S ⊂ T: for all x in S, x is also in T ● Example: S = {a,b} aaba, baaa, aaba ∈S* aaba|baaa|aaba ∈S** a|a|b|a|b|a|a|a|a|a|b|a ∈S* 16

● Theorem 1: S**=S* ● Proof:  Case 1: S** ⊂ S* Every word in S** is made up of factors from S* (definition of Kleene star). Every word in S* is made up of factors from S. Therefore, every word in S** is also a word in S*. Thus S** ⊂ S*.  Case 2: S* ⊂ S** For any set A, we can show that A ⊂ A*. Let w be a word in A. Then w is certainly in A*. If we consider S* as our set A, we can conclude S* ⊂ S**. By definition of equality of sets, we have S* = S**. 17


CSI3104 Introduction to Formal Languages Lecture Notes

CSI3104 Introduction to Formal Languages Lecture Notes Amy Felty Winter 2017 I. Theory of Automata II. Theory of Context-Free Languages III. Theory of...

84KB Sizes 1 Downloads 11 Views

Recommend Documents

An Introduction to Formal Languages and Automata
An Introduction to. FORMAL LANGUAGES and AUTOMATA. Fifth Edition. PETER LINZ. University of California at Davis. JONES &

Introduction to Macroeconomics Lecture Notes
unemployment (around 5%), good economic growth, and inflation (0—3%). In all specifications, aim is meeting several co

Introduction to Christian Theology – Lecture Notes
Some introduction courses end up being one big excursus on “how to” or “how should” one do theology. This course

STAT 6200 | Introduction to Biostatistics Lecture Notes
Lecture Notes. Introduction*. Statistics and Biostatistics: The field of statistics: The study and use of theory and met

MPRI Lecture Notes Cryptographic protocols Formal and
In [120], a list of some relevant algebraic properties of cryptographic operators is given, and for each of them, some e

Introduction to Geophysics – Lecture Notes
Mar 23, 2015 - We have a rock sample and we have measured the value of density to be 2.60 g/cm3. According to this value

Introduction to Software Engineering: Lecture Notes
Lecture 01: Introduction to Software Engineering - 1. http://ocw.kfupm.edu.sa/ocw_courses/phase2/SWE205/Lecture%20Notes/

CS 540 Lecture Notes: Introduction
Another answer: "It is the science and engineering of making intelligent machines, especially intelligent computer progr

Lecture Notes: Introduction - Phil Ender
Lecture Notes. Lectures will be used in class. Lectures will be available on the Multivariate Course Web site. About Ass

CSCI200 - Introduction to Computers (Lecture Notes) 1. Introduction
CSCI200 – Introduction to Computers (Lecture Notes) CSCI200 - Introduction to Computers (Lecture Notes) 1. Introductio