Transcript Slide 1 - دانشگاه صنعتی شریف

‫نظریه زبان ها و ماشین ها‬
‫فصل صفر‪ -‬مقدمه‬
‫دانشگاه صنعتی شریف‬
‫نیمسال ّاول سال تحصیلی ‪1388‬‬
‫مراجع درس‬
:‫• مرجع اصلی‬
M. Sipser, ”Introduction to the Theory of Computation,” 2nd Ed.,
Thompson Learning Inc., 2006.
:‫• مراجع کمکی‬
P. Linz, “An Introduction to Formal Languages and Automata,” 3rd
Ed., Jones and Barlett Publishers, Inc., 2001.
J.E. Hopcroft, R. Motwani and J.D. Ullman, “Introduction to
Automata Theory, Languages, and Computation,” 2nd Ed., Addison
Wesley, 2001.
P.J. Denning, J.B. Dennnis, and J.E. Qualitz, “Machines,
Languages, and Computation,” Prentice-Hall, Inc., 1978.
P.J. Cameron, “Sets, Logic and Categories,” Springer-Verlag,
London limited, 1998.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
‫سیاست نمره دهی درس‬
‫• تمرینات ‪15%‬‬
‫• ارائه تحقیقاتي ‪10%‬‬
‫• کوییز ‪ 1‬عمومی درس ‪20%‬‬
‫• کوییز ‪ 2‬عمومی درس ‪25%‬‬
‫• آزمون پایان نیمسال ‪30%‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫نظریه پیچیدگی‬
‫• دانش رده بندی مسائل بر اساس سختی محاسباتی‬
‫• برای غلبه بر پیچیدگی چه می توان کرد؟‬
‫–‬
‫–‬
‫–‬
‫–‬
‫تغییر مسئله پس از کشف که عامل دشواری آن‬
‫تقریب زدن راه حل مسئله‬
‫ارائه روش هایی که در حالت متوسط عملکرد خوبی دارند؛‬
‫استفاده از روش های تصادفی‬
‫• کاربردها‬
‫– به عنوان مثال در رمزنگاری‪ ،‬هدف این است که رمزگشایی با توان‬
‫محاسباتی مهاجم غیرممکن باشد‪.‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫عناوین مورد بحث‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫نظریه پیچیدگی‬
‫نظریه محاسبه پذیری‬
‫نظریه ماشین ها‬
‫مبانی ریاضی‬
‫الفبا‬
‫رشته ها‬
‫زبان ها‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫نظریه محاسبه پذیری‬
‫• ماشین ها چه مسائلی را می توانند حل کنند؟‬
‫• رده بندی مسائل در دو گروه قابل محاسبه و غیرقابل محاسبه‬
‫• مدل های نظری برای ماشین ها‬
‫– به علت قدرتمندی مدل هایی مانند ‪ RAM‬یا ماشین تورینگ اثبات این که چه‬
‫مسائلی را می توانند حل کنند دشوار است‪.‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫نظریه ماشین ها‬
‫• تعریف و ویژگی های مدل های ریاضی محاسبه‬
‫– مدل ماشین حالت متناهی‬
‫• در پردازش متن‪ ،‬کامپایلرها و طراحی سخت افزار کاربرد دارد‪.‬‬
‫– مدل ماشین پشته ای‬
‫• در زبان های برنامه سازی و هوش مصنوعی کاربرد دارد‪.‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
Logic
A Brief History of Logic
• Definition: Logic is the science of the
formal principles of reasoning.
• Logic was known as 'dialectic' or 'analytic'
in Ancient Greece. The word 'logic' (from
the Greek logos, meaning discourse or
sentence) does not appear in the modern
sense until the commentaries of Alexander
of Aphrodisias, writing in the third century
A.D.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
A Brief History of Logic
• While many cultures have employed intricate
systems of reasoning, and logical methods are
evident in all human thought, an explicit analysis
of the principles of reasoning was developed only
in three traditions: those of China, India, and
Greece.
• Although exact dates are uncertain, particularly
in the case of India, it is possible that logic
emerged in all three societies by the 4th century
BC.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
A Brief History of Logic
• The formally sophisticated treatment of modern
logic descends from the Greek tradition,
particularly Aristotelian logic, which was further
developed by Islamic Logicians and then
medieval European logicians.
• The work of Frege in the 19th century marked a
radical departure from the Aristotlian leading to
the rapid development of symbolic logic, later
called mathematical logic.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Modern Logic
• Descartes proposed using algebra, especially
techniques for solving for unknown quantities in
equations, as a vehicle for scientific exploration.
• The idea of a calculus of reasoning was also
developed by Leibniz. He was the first to
formulate the notion of a broadly applicable
system of mathematical logic.
• Frege in his 1879 work extended formal logic
beyond propositional logic to include
quantification to represent the "all", "some"
propositions of Aristotelian logic.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Modern Logic
• A logic is a language of formulas.
• A formula is a finite sequence of
symbols with a syntax and
semantics.
• A logic can have a formal system.
• A formal system consists of a set of
axioms and rules of inference.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Logic Types of Interest
•Propositional Logic
•Predicate Logic
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Syntax of Propositional Logic
• Let {p0, p1, ..} be a countable set of
propositional variables,
• {, , ¬, →, ↔} be a finite set of
connectives,
• Also, there are left and right brackets,
• A propositional variable is a formula,
• If φ and ψ are formulas, then so are (¬φ), (φ 
ψ), (φ  ψ), (φ → ψ), and (φ ↔ ψ).
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Semantics of Propositional
Logic
• Any formula, which involves the
propositional variables p0,...,pn , can
be used to define a function of n
variables, that is, a function from the
set {T, F}n to {T, F}. This function is
often represented as the truth table
of the formula and is defined to be
the semantics of that formula.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
‫)‪Examples: (φ  ψ‬‬
‫)‪(φ  ψ‬‬
‫‪ψ‬‬
‫‪φ‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪F‬‬
‫‪F‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫)‪Examples: (φ  ψ‬‬
‫)‪(φ  ψ‬‬
‫‪ψ‬‬
‫‪φ‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫نظریه زبان ها و ماشین ها‬
‫‪‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪F‬‬
‫‪F‬‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫)‪Examples: (φ → ψ‬‬
‫)‪(φ → ψ‬‬
‫‪ψ‬‬
‫‪φ‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫نظریه زبان ها و ماشین ها‬
‫‪‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫)‪Examples: (φ ↔ ψ‬‬
‫)‪(φ ↔ ψ‬‬
‫‪ψ‬‬
‫‪φ‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫نظریه زبان ها و ماشین ها‬
‫‪‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫)‪Example: (¬φ‬‬
‫نظریه زبان ها و ماشین ها‬
‫)‪(¬φ‬‬
‫‪φ‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
Other Definitions
• A formulae is a tautology if it is
always true.
• A formulae is a contradiction if it is
never true.
• A formulae is a contingency if it is
sometimes true.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Examples
• (P  (¬P)) is a tautology.
• (P  (¬P)) is a contradiction.
•(P → (¬P)) is a contingency.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Formal System
A formal system includes the following:
• An alphabet A, a set of symbols.
• A set of formulae, each of which is a string
of symbols from A.
• A set of axioms, each axiom being a
formula.
• A set of rules of inference, each of which
takes as ‘input’ a finite sequence of
formulae and produces as output a formula
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Proof
• A proof in a formal system is just
a finite sequence of formulae
such that each formula in the
sequence either is an axiom or is
obtained from earlier formulae
by applying a rule of inference.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Theorem
•A theorem of the formal
system is just the last
formula in a proof.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
A Formal System for
Propositional Logic
 There are three ‘schemes’ of axioms,
namely:
 (A1) (φ→(ψ → φ))
 (A2) (φ→(ψ → θ)) → ((φ→ ψ) → (φ → θ))
 (A3) (((¬φ) →(¬ψ)) → (ψ → φ))
 Each of these formulas is an axiom, for all
choices of formulae φ, ψ, θ.
 There is only one rule of inference, namely
Modus Ponens: From φ and (φ→ ψ), infer ψ.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Example of a Theorem
•For any formula φ, the
formula (φ→φ) is a theorem
of the propositional logic.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Example of a Proof
• Using (A2), taking φ, ψ, θ to be φ, (φ→φ) and φ
respectively
((φ→((φ→φ)→φ))→((φ→(φ→φ))→(φ →φ)))
• Using (A1), taking φ, ψ to be φ and (φ→φ) respectively
(φ→((φ→φ)→φ))
• Using Modus Ponens
((φ→(φ→φ))→(φ →φ))
• Using (A1), taking φ, ψ to be φ and φ respectively
(φ→(φ→φ))
• Using Modus Ponens
(φ→φ)
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Soundness and
Completeness
• A formal system is said to be
sound if all theorems in that
system are tautology.
• A formal system is said to be
complete if all tautologies in
that system are theorems.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Predicate
• A proposition involving some
variables, functions and relations
• Example:
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
‫‪Quantifiers‬‬
‫•‬
‫•‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫‪Quantifiers: Negation‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫قواعد استنتاج‬
‫‪.1‬‬
‫‪.2‬‬
‫‪.3‬‬
‫‪.4‬‬
‫‪.5‬‬
‫‪Modus ponens‬‬
‫برهان خلف‬
‫‪Conjunction‬‬
‫اثبات با مورد‬
‫استقراء‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
Direct Proof
• If the two propositions (premises) p
and p → q are theorems, we may
deduce that the proposition q is also a
theorem.
• This fundamental rule of inference is
called modus ponens by logicians.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Indirect Proof
• Proves p → q by instead proving
the contra-positive, ~q → ~p
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Proof by Contradiction
• The rule of inference used is that
from theorems p and ¬q → ¬p,
we may deduce theorem q.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Proof By Cases
• You want to prove p → q
• P can be decomposed to some cases:
p ↔ p1 ν p2 ν …ν pn
• independently prove the n implications
given by
pi → q for 1 ≤ i ≤ n.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Constructive Existence Proof
• Want to prove that  x P(x) .
• Find an a and then prove that
P(a) is true
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
‫اثبات با استقراء‬
‫) ‪xP (x‬‬
‫‪• To prove‬‬
‫‪• 1) Proof P(0),‬‬
‫])‪• 2) Proof x [P (x )  P (x  1‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
Non-Constructive Existence Proof
• Want to prove that  x P(x) .
• You cannot find an a that P(a) is
true
• Then, you can use proof by
contradiction:
~  x P ( x)   x ~ P( x)  F
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Intuitive (Naïve) Set
Theory
There are three basic concepts in set
theory:
• Membership
• Extension
• Abstraction
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Membership
Membership is a relation that holds between a set and an object
to mean “the object x is a member of the set A”, or “x belongs to
A”. The negation of this assertion is written
as an abbreviation for the proposition
One way to specify a set is to list its elements. For example, the se
A = {a, b, c}
consists of three elements. For this set A, it is true that
but
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Extension
The concept of extension is that two sets are identical
if and if only if they contain the same elements. Thus
we write A=B to mean
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Abstraction
Each property defines a set, and each set defines a
property
• If p(x) is a property then we can define a set A
• If A is a set then we can define a predicate p(x)
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Intuitive versus axiomatic set theory
• The theory of set built on the intuitive
concept of membership, extension, and
abstraction is known as intuitive (naïve)
set theory.
• As an axiomatic theory of sets, it is not
entirely satisfactory, because the principle
of abstraction leads to contradictions when
applied to certain simple predicates.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Russell’s Paradox
Let p(X) be a predicate defined as
P(X) = (XX)
Define set R as
R={X|P(X)}
• Is P(R) true?
• Is P(R) false?
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Gottlob Frege’s Comments
• The logician Gottlob Frege was the first to
develop mathematics on the foundation of set
theory. He learned of Russell Paradox while his
work was in press, and wrote, “A scientist can
hardly meet with anything more undesirable than
to have the foundation give way just as the work
is finished. In this position I was put by a letter
from Mr. Bertrand Russell as the work was nearly
through the press.”
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Power Set
The set of all subsets of a given set A is
known as the power set of A, and is
denoted by P(A):
P(A) = {B | B  A}
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Set Operation-Union
• The union of two sets A and B is
A  B = {x | (x  A)  (x  B)}
and consists of those elements in at least one of A
and B.
• If A1, …, An constitute a family of sets, their union is
= (A1  …  An)
= {x| x  Ai for some i, 1≤ i ≤ n}
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Set Operation-Intersection
• The intersection of two sets A and B is
A  B = {x | (x  A) (x  B)}
and consists of those elements in at least one of A and B.
• If A1, …, An constitute a family of sets, their intersection is
= (A1  …  An)
= {x| x  Ai for all i, 1≤ i ≤ n}
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Set Operation-Complement
• The complement of a set A is a set Ac defined as:
Ac = {x | x A}
• The complement of a set B with respect to A, also
denoted as A-B, is defined as:
Ac = {x A | x B}
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫ها و ماشین ها‬
Ordered Pairs and n-tuples
• An ordered pair of elements is written
(x,y)
where x is known as the first element, and y is known
as the second element.
• An n-tuple is an ordered sequence of elements
(x1, x2, …, xn)
And is a generalization of an ordered pair.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Ordered Sets and Set
Products
• By Cartesian product of two sets A and B, we mean
the set
A×B = {(x,y)|xA , yB}
• Similarly,
A1×A2×…An = {x1A1, x2A2, …, xnAn}
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Relations
A relation ρ between sets A and B is a subset of A×B:
ρ  A×B
• The domain of ρ is defined as
Dρ = {x  A | for some y  B, (x,y)  ρ}
• The range of ρ is defined as
Rρ = {y  B | for some x  A, (x,y)  ρ}
• If ρ  A×A, then ρ is called a ”relation on A”.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Types of Relations on Sets
• A relation ρ is reflexive if
(x,x) ρ, for each xA
• A relation ρ is symmetric if, for all x,yA
(x,y) ρ implies (y,x) ρ
• A relation ρ is antisymmetric if, for all x,yA
(x,y) ρ and (y,x) ρ implies x=y
• A relation ρ is transitive if, for all x,y,zA
(x,y) ρ and (y,z) ρ implies (x,z) ρ
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Partial Order and
Equivalence Relations
• A relation ρ on a set A is called a
partial ordering of A if ρ is reflexive,
anti-symmetric, and transitive.
• A relation ρ on a set A is called an
equivalence relation if ρ is reflexive,
symmetric, and transitive.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Total Ordering
• A relation ρ on a set A is a total ordering if
ρ is a partial ordering and, for each pair of
elements (x,y) in A×A at least one of
(x,y)ρ or (y,x)ρ is true.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Inverse Relation
• For any relation ρ  A×B, the inverse of
ρ is defined by
ρ-1 = {(y,x) | (x,Y)  ρ}
• If Dρ and Rρ are the domain and range
of ρ, then
Dρ-1 = Dρ and Rρ-1 = Rρ
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Equivalence Class
• Let ρ  A×A be an equivalence relation
on A. The equivalence class of an
element x is defined as
[x] = {y  A | (x,y)  ρ}
• An equivalence relation on a set
partitions the set.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Functions
A relation f  A× B is a function if it has the property
(x,y) f and (x,z) f implies y=z
• If f  A× B is a function, we write
f: A → B
and say that f maps A into B. We use the common notation
Y = f(x)
to mean (x,y)  f.
• As before, the domain of f is the set
Df = {x A | for some y B, (x,y)  f}
and the range of f is the set
Rf = {y B | for some x  A, (x,y)  f}
• If Df  A, we say the function is a partial function; if Df = A, we say
that f is a total function.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Functions (continued)
• If x  Df, we say that f is defined at x; otherwise
f is undefined at x.
• If Rf = B, we say that f maps Df onto B.
• If a function f has the property
f(x) = z and f(y) = z implies x = y
then f is a one-to-one function. If f: A → B is a
one-to-one function, f gives a one-to-one
correspondence between elements of its domain
and range.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Functions (continued)
• Let X be a set and suppose A  X. Define function
CA: X → {0,1}
such that CA(x) = 1, if x A; CA(x) = 0, otherwise. CA(x) is called
the characteristic function of set A with respect to set X.
• If f  A× B is a function, then the inverse of f is the set
f-1 = {(y,x) | (x,y)  f}
f-1 is a function if and only if f is one-to-one.
• Let f: A → B be a function, and suppose that X  A. Then the set
Y = f(X) = {y  B | y = f(x) for some x  X}
is known as the image of X under f.
• Similarly, the inverse image of a set Y included in the range of f is
f-1(Y) = {x  A | y = f(x) for some y  Y}
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Cardinality
• Two sets A and B are of equal cardinality, written as
|A| = |B|
if and only if there is a one-to-one function f: A → B
that maps A onto B.
• We write
|A| ≤ |B|
if B includes a subset C such that |A| = |C|.
• If |A| ≤ |B| and |A| ≠ |B|, then A has cardinality less
than that of B, and we write
|A| < |B|
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Cardinality (continued)
• Let J = {1, 2, …} and Jn = {1, 2, …, n}.
• A sequence on a set X is a function f: J → X. A
sequence may be written as
f(1), f(2), f(3), …
However, we often use the simpler notation
x1, x2, x3, ….,
xi  X
• A finite sequence of length n on X is a function
f: Jn → X, usually written as
x1, x2, x3, …., xn,
xi  X
• The sequence of length zero is the function f: → X.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Finite and Infinite Sets
• A set A is finite if |A| = |jn| for some
integer n≥0, in which case we say that A
has cardinality n.
• A set is infinite if it is not finite.
• A set X is denumerable if |X| = |j|. A set
is countable if it is either finite or
denumerable.
• A set is uncountable if it is not countable.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Some Properties
• Proposition: Every subset of J is countable.
Consequently, each subset of any denumerable
set is countable.
• Proposition: A function f: J → Y has a countable
range. Hence any function on a countable
domain has a countable range.
• Proposition: The set J × J is denumerable.
Therefore, A × B is countable for arbitrary
countable sets A and B.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Some Properties
• Proposition: The set A  B is countable
whenever A and B are countable sets.
• Proposition: Every infinite set X is at least
denumerable ; that is |X| ≥ |J|.
• Proposition: The set of all infinite sequence on
{0, 1} is uncountable.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
Some Properties
• Proposition: (Schröder-Bernestein Theorem)
For any set A and B, if |A| ≥ |B| and |B| ≥ |A|,
then |A| = |B|.
• Proposition: (Cantor’s Theorem)
For any set X,
|X| < |P(X)|.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬
‫‪*1-1 correspondence Q↔N‬‬
‫‪• Proof (dove-tailing):‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
Countable Sets
•
•
•
•
•
•
88
Any subset of a countable set
The set of integers, algebraic/rational numbers
The union of two/finite number of countable sets
Cartesian product of a finite number of countable sets
The set of all finite subsets of N;
Set of binary strings
‫نیمسال ّاول‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫‪Diagonal Argument‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫نیمسال ّاول‬
‫‪88‬‬
Uncountable Sets
•
•
•
•
•
•
88
R, R2, P(N)
The intervals [0,1), [0, 1], (0, 1)
The set of all real numbers;
The set of all functions from N to {0, 1};
The set of functions N → N;
Any set having an uncountable subset
‫نیمسال ّاول‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
Transfinite Cardinal Numbers
• Cardinality of a finite set is simply the number of
elements in the set.
• Cardinalities of infinite sets are not natural numbers, but
are special objects called transfinite cardinal numbers
• 0:|N|, is the first transfinite cardinal number.
• continuum hypothesis claims that |R|=1, the second
transfinite cardinal.
88
‫نیمسال ّاول‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫الفبا‬
‫• الفبا‬
‫– مجموعه ای متناهی ‪ ,‬و غیرتهی از عالئم الفبایی (معموالً با‬
‫∑ یا ‪ Г‬نمایش داده می شود)‬
‫– مثال‪:‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫رشته ها‬
‫• رشته‬
‫–‬
‫–‬
‫–‬
‫–‬
‫دنباله ای متناهی از عالئم یک الفبا‬
‫مثال‪:‬‬
‫طول رشته ‪ ω‬که با |‪ |ω‬نشان داده می شود تعداد عالئم موجود در رشته‬
‫است‪.‬‬
‫رشته تهی(‪ ε‬یا ‪ )λ‬رشته ای با طول صفر است‪.‬‬
‫– یک زیررشته(‪ )substring‬زیردنباله ای شامل عالئم متوالی از رشته‬
‫است‪.‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫اعمال روی رشته ها‬
‫• مقلوب یک رشته‬
‫– مثال‪:‬‬
‫• الحاق رشته ها‬
‫– مثال‪:‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫اعمال روی الفبا‬
‫• عملگر *‪:‬‬
‫– مجموعه تمام رشته هایی که از الفبای ∑ قابل تولید هستند‪.‬‬
‫• عملگر ‪:+‬‬
‫– مجموعه تمام رشته ها به جز ‪ λ‬که از الفبای ∑ قابل تولید هستند‪.‬‬
‫فرض کنید }‪ . = {λ‬آنگاه‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫زبان ها‬
‫• زبان‬
‫– مجموعه ای از رشته ها روی یک الفبای معین‬
‫– هر زبان روی یک الفبای ∑‪ ،‬زیر مجموعه ای از *∑ است‪.‬‬
‫– مثال‪:‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫اعمال روی زبان ها‬
‫• زبان ها نوعی خاص از مجموعه هستند و اعمال روی مجموعه ها‬
‫در آن ها نیز قابل تعریف است‪.‬‬
‫– اجتماع‬
‫– اشتراک‬
‫– تفاضل‬
‫– متمم‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫اعمال روی زبان ها‬
‫• مقلوب یک زبان‪:‬‬
‫– مثال‪:‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫اعمال روی زبان ها‬
‫• الحاق(‪ )Concatenation‬دو زبان‪:‬‬
‫– مثال‪:‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
‫اعمال روی زبان ها‬
‫•‬
‫عملگر *‬
‫(* ‪:)Kleene‬‬
‫– مجموعه تمام رشته هایی که با الحاق رشته های یک زبان قابل تولید هستند‪.‬‬
‫– مثال‪:‬‬
‫• عملگر ‪ +‬نیز مانند عملگر * است با این تفاوت که رشته ‪ λ‬در مجموعه حاصل‬
‫نیست‪.‬‬
‫نظریه زبان ها و ماشین ها‬
‫دانشگاه صنعتی شریف‬
‫اول ‪88‬‬
‫نیمسال ّ‬
Gödel Numbering
• Let  be an alphabet containing n objects. Let h:  → Jn be an
arbitrary one-to-one correspondence. Define function f as:
f:  → N
such that f(ε) =0; f(w.v) = n f(w) + h(v), for w  and v .
f is called a Gödel Numbering of  .
*
*
*
• Proposition: 
*
is denumerable.
• Proposition: Any language on an alphabet is countable.
88 ‫اول‬
ّ ‫نیمسال‬
‫دانشگاه صنعتی شریف‬
‫نظریه زبان ها و ماشین ها‬