Free Download of VTU 5th Semester Computer Science FAFL Automata related Projects. Do put on a comment to start downloading.
Download here it for free. Free Download here.
Catch me at: http://firstvikram.synthasite.com
and also at : http://tvvikram.blogspot.com
Contents
1 Formal languages 2
1.1 For the English Language: . . . . . . . . . . . . . . . . . . . . 2
1.2 Finite-State Grammars . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The general form of finite state grammars . . . . . . . . . . . 3
1.4 The Chomsky Hierarchy . . . . . . . . . . . . . . . . . . . . . 4
2 Different Proving Techniques 5
2.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Example: . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Deduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Deduction Logic . . . . . . . . . . . . . . . . . . . . . . 7
3 Automata of an Automated Teller Machine - ATM 9
1
Formalization of natural languages using formal structure
1 Formal languages
In formal language theory, a language is a set of strings. A string is just a
sequence of symbols chosen from an agreed-upon set of symbols, called the
vocabulary or lexicon.
1.1 For the English Language:
• Any sequence of English words from the Oxford English Dictionary like
what a language!, books written knowledge people are examples whereas We
sdf hit iflas bgow sil will not make English a formal language.
• Strings over {a, b, c} starting with a like abbb, a, a followed by a million
bs is an example whereas bcacc, the zero-length string epsilon.
• Strings over {a, b, c, d} in alphabetical order like abd, ad, bcd, b, abcd
are examples whereas dbcd, ba.
All the examples are defined with rules given before each example. The
idea of generative grammar is to use grammars to define a set that closely
resembles a natural language for instance, all and only the acceptable English
sentences. However, not all sets are definable by all types of grammars. We
require a set of rules to accurately describe a natural language.
1.2 Finite-State Grammars
To generate strings over {a, b, c, d} in alphabetical order, let S be the start
symbol of the grammar.
S → a S1
S → b S2
S → c S3
S→d
S1 → b S2
S1 → c S3
S1 → d
S2 → c S3
S2 → d
S3 → d
2
Grammar has a corresponding finite state machine that recognizes all and
only the sentences it generates.
1.3 The general form of finite state grammars
Any grammar having only rules of the form A → bC where A,B are nonter-
minals and b is a terminal has a corresponding finite state machine. Given
a string, if a path can be found through the machine, the string is generated
by the grammar and vice versa. There are some languages that cannot be
recognized by finite state machines.
Sequence of as followed by an equal number of bs like ab, aabb, aaabbb,
. . . is an example whereas aabbb, aaaaaaaaaaaabbb do not form the grammer
as per the rule.
Call the number of as in the sentence being analyzed n. A finite state
machine would need to remember this number n while waiting for the end
of the bs. But, by definition, a finite state machine will only have enough
states to remember some fixed number of as. Hence there exists neither a
finite-state grammar nor a finite state machine for the language an bn .
English is just like an bn
Consider
a. The cat died.
b. The cat the dog chased died.
c. The cat the dog the rat bit chased died.
d. The cat the dog the rat the elephant admired bit chased died
...
f A = {the cat, the dog, the rat, the elephant, the kangaroo, . . .} and
B = {chased, bit, admired, ate, befriended, . . .} its clear that it has the
structure an bn died.
Chomsky and Miller (1963) argued that the obligatory paired dependen-
cies presented by either. . .or, if. . .then or the agreement between verbs and
subjects can nest inside one another to an arbitrary depth.
The following grammar does not generate the language an bn . It is a
context-free grammar, and as such is capable of deriving any number of
center-embeddings.
S→ab
S→aSb
3
1.4 The Chomsky Hierarchy
Let A,B be nonterminals, b a terminal, alpha nonempty sequence of either
kind of symbol, and , γ, δ possibly empty sequences of either kind of symbol.
The Chomsky Hierarchy is a classification of languages in a subset relation-
ship. Each language has corresponding class of machine that recognizes it.
language attribute rule type machine
A →bC
finite-state finite state machine
A→α
context-free push down automata
γ A δ → γαδ
context-sensitive linear bounded
automation unrestricted no restrictin Turing machine
The cardinality of the set of languages definable by a grammar formalism
is called its generative capacity.
Natural languages are believed to reside somewhere between context-free and
context-sensitive.
Source: Internet
4
2 Different Proving Techniques
2.1 Mathematical Induction
Mathematical induction is a method of mathematical proof typically used to
establish that a given statement is true of all natural numbers. It is done
by proving that the first statement in the infinite sequence of statements is
true, and then proving that if any one statement in the infinite sequence of
statements is true, then so is the next one.
The method can be extended to prove statements about more general
well-founded structures, such as trees; this generalization, known as struc-
tural induction, is used in mathematical logic and computer science. Math-
ematical induction in this extended sense is closely related to recursion.
2.1.1 Description
The simplest and most common form of mathematical induction proves that
a statement involving a natural number n holds for all values of n. The proof
consists of two steps:
1. The basis (base case): showing that the statement holds when n = 0
or n = 1.
2. The inductive step: showing that if the statement holds for some n, then
the statement also holds when n + 1 is substituted for n.
The assumption in the inductive step that the statement holds for some
n is called the induction hypothesis (or inductive hypothesis). To perform
the inductive step, one assumes the induction hypothesis and then uses this
assumption to prove the statement for n + 1.
The description above of the basis applies when 0 is considered a natural
number, as is common in the fields of combinatorics and mathematical logic.
If, on the other hand, 1 is taken to be the first natural number, then the base
case is given by n = 1.
This method works by first proving the statement is true for a starting
value, and then proving that the process used to go from one value to the
next is valid. If these are both proven, then any value can be obtained by
performing the process repeatedly. It may be helpful to think of the domino
effect; if one is presented with a long row of dominoes standing on end, one
can be sure that:
1. The first domino will fall.
2. Whenever a domino falls, its next neighbour will also fall.
So it is concluded that all of the dominoes will fall, and that this fact is
inevitable.
5
2.2 Contradiction
In logic, proof by contradiction is a form of proof that establishes the truth
or validity of a proposition by showing that the premise that the proposition
is false implies a contradiction. Since by the law of bivalence a proposition
must be either true or false, and its falsity has been shown impossible, the
proposition must be true.
In other words, to prove by contradiction that P, show that ¬ P ⇒⊥ or
its equivalent ¬ P ⇒ (Q ∧ ¬ Q). Then, since ¬ P implies a contradiction,
conclude P.
Proof by contradiction is also known as indirect proof, apagogical argu-
ment, reductio ad impossibile, or reductio ad absurdum.
In a proof by contradiction we assume, along with the hypotheses, the
logical negation of the result we wish to prove, and then reach some kind of
contradiction. That is, if we want to prove ”If P, Then Q”, we assume P and
Not Q. The contradiction we arrive at could be some conclusion contradicting
one of our assumptions, or something obviously untrue like 1 = 0.
2.2.1 Example:
A classic proof by contradiction from Greek mathematics is the proof that
the square root of 2 is irrational. If it were rational, it could be expressed
as a fraction a/b in lowest terms, where a and b are integers, at least one of
√
which is odd. But if a/b = 2, then a2 = 2b2 . Therefore a2 must be even.
Because the square of an odd number is odd, that in turn implies that a is
even. This means that b must be odd because a/b is in lowest terms.
On the other hand, if a is even, then a2 is a multiple of 4. If a2 is a
multiple of 4 and a2 = 2b2 , then 2b2 is a multiple of 4, and therefore b2 is
even, and so is b.
So b is odd and even, a contradiction. Therefore the initial assumption-
√
that 2 can be expressed as a fractionmust be false. One of the first proofs
by contradiction is the following gem attributed to Euclid.
Theorem: There are infinitely many prime numbers.
Proof : Assume to the contrary that there are only finitely many prime
numbers, and all of them are listed as follows:
p1, p2 ..., pn. Consider the number q = p1p2... pn + 1.The number q is
either prime or composite. If we divide any of the listed primes pi into q,
this would result in a remainder of 1 for each i = 1, 2, ..., n. Thus, q cannot
be composite.
We conclude that q is a prime number, not among the primes listed above,
6
contradicting our assumption that all primes are in the list p1, p2 ..., pn.
Proof by contradiction is often used when we wish to prove the impossibility
of something.
2.3 Deduction
In logic, natural deduction is an approach to proof theory that attempts to
provide a deductive system which is a formal model of logical reasoning as it
”naturally” occurs. This approach is in contrast to axiomatic systems which
use axioms.
2.3.1 Deduction Logic
The nine primitive rules
1. The Rule of Assumption (A)
2. Modus Ponendo Ponens (MPP)
3. The Rule of Double Negation (DN)
4. The Rule of Conditional Proof (CP)
5. The Rule of -introduction (I)
6. The Rule of -elimination (E)
7. The Rule of -introduction (I)
8. The Rule of -elimination (E)
9. Reductio Ad Absurdum (RAA)
In system L, a proof has a definition with the following conditions:
1. has a finite sequence of well-formed formulas (or wffs)
2. each line of it is justified by a rule of the system L
3. the last line of the proof is what is intended, and this last line of the proof
uses only the premises which were given, if any.
An example of the proof of a sequent
p → q, ¬q ¬p [Modus Tollendo Tollens (MTT)]
7
Assumption number Line number Formula (wff) Lines in-use and Justification
1 (1) (p→q) A
¬q
2 (2) A
3 (3) p A(For RAA)
1,3 (4) q 1,3,MPP
q∧ ¬q
1,2,3 (5) 2,4
¬p
1,2 (6) 3,5,RAA
Q.E.D
A deduction (or proof) can be defined precisely in the context of a formal
system like the propositional calculus. A proposition is deduced from a col-
lection of premises by applying inference rules repeatedly. The deduction is
a record of this repeated application of inference rules.
Source: Internet
8
3 Automata of an Automated Teller
Machine - ATM
An Automated Teller Machine is one of the automata thats too common in
real life. It follows the following automata to validate the card and execute
the transaction.
• It accepts the card.
• Validates the card with the server. The server authorises the card.
• If the card is invalid, it enters the trap state.
• On succesful validation of the card, it asks for the user to input the secret
PIN provided.
User Inputs PIN. The PIN’s validity is matched with the card from the
server.
• Ater the PIN is accepted and the card is found to be valid, and thus the
user is valid, it asks for the transaction to happen.
In case of withdrawal it asks for amount to withdraw. Checks for suffi-
cient balance and if user doesnot have, it aborts the transaction.
Otherwise the amount is deducted from user’s account database. The
amount is handed over to the user and transaction is closed.
The automata for the ATM can be represented as shown in graph.
9
Figure 1: Automata of an ATM
Source: Internet
10
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment