UNIT-1�INTRODUCTION TO

FINITE AUTOMATA��PREPARED BY:SRIRAM

Alphabet

An alphabet is a finite and non empty set of symbols.

The example of alphabet is,

S={a, b, c,……..z}

The elements a, b, c, …….z are alphabets.

​

If W={0,1}

Here 0 and 1 are alphabets, denoted by W.

String

TOC SP CHARI

• It is finite collection of symbols from alphabet.

For example, if Σ = {a,b} then various strings that can be formed from Σ are {ab, ba, aaa, bbbb, aba, bab, ….}. An infinite number of strings can be generated.

Language

• The language is a collection of appropriate strings.
• The language is defined using an input set. The input set is typically denoted by letter Σ.

For example: Σ ={Ꜫ,0,00,000,0000,….}.

Here the language L is defined as ‘Any number of Zeros’.

Examples

TOC SP CHARI

1. The set of all strings over {a,b,c} that have ac as substring can be written as {xacy | x,y ∈{a,b,c}∗}.

This can also be written as {x∈{a,b,c}∗ ||x|_ac ≥1},

stating that the set of all strings over {a,b,c} in which the number of occurrences of substring ac is at least 1.

2. The set of all strings over some alphabet Σ with even number of a’s is {x∈Σ∗ ||x|_a = 2n, for some n∈N}.

Equivalently, {x∈Σ∗ ||x|_a ≡ 0 mod 2}.

3. The set of all strings over some alphabet Σ with equal number

of a’s and b’s can be written as {x∈Σ∗ ||x|_a =|x|_b}.

4. The set of all palindromes over an alphabet Σ can be written as

{x∈Σ∗ | x = x^R}, where x^R is the string obtained by reversing x.

Finite State Machine

TOC notes by S P CHARI

• The finite state machine represents a mathematical model of a system with certain input.

​

• The model finally gives certain output.

​

• The input is processed by various states, these states are called as intermediate states.

​

• The finite state system is very good design tool for the programs such as TEXT EDITORS and LEXICAL ANALYZERS.

Definition of Finite Automata

TOC notes by S P CHARI

• A finite automata is a collection of 5-tuple(Q,Σ,δ,q₀,F) Where , Q is finite set of states, which is non empty.

Σ is input alphabet, indicates input set.

δ is transition function or mapping function. We can determine the next state using this function.

q₀ is an initial state and is in Q F is set of final states.

Finite Automata Model

TOC notes by S P CHARI

• The finite automata can be represented as follows:

Input Tape

​

​

Finite

Control

Tape

Reader

• Input Tape: It is a linear tape having some number of cells. Each input symbol is placed in each cell.

• Finite Control: The finite control decides the next state on receiving particular input from input tape.

Out put

Types of Automata

TOC notes by S P CHARI

Finite Automata

Deterministic Finite Automata

Non Deterministic Finite Automata

Types of Automata

• Deterministic Finite Automata: The Finite Automata is called Deterministic Finite Automata if there is only one path for a specific input from current state to next state.

It can be represented as follows:

• A machine M = (Q,Σ,δ,q₀,F) Where ,

Q is finite set of states, which is non empty.

Σ is input alphabet, indicates input set.

δ is transition function or mapping function. We can determine the next state using this function.

q₀ is an initial state and is in Q F is set of final states.

Where δ:Q X Σ -> Q

TOC notes by S P CHARI

KMIT

Types of Automata

• Non Deterministic Finite Automata: The Finite Automata is called Non Deterministic Finite Automata if there are more than one path for a specific input from current state to next state.

It can be represented as follows:

• A machine M = (Q,Σ,δ,q₀,F) Where ,

Q is finite set of states, which is non empty.

Σ is input alphabet, indicates input set.

δ is transition function or mapping function. We can determine the next state using this function.

q₀ is an initial state and is in Q F is set of final states.

_{Where δ:Q X Σ -> 2}TO_QC notes by Pallavi Joshi

Difference between DFA & NFA

TOC notes by S P CHARI

Hierarchy of languages

TOC notes by S P CHARI

Recursively Enumerable Languages

Recursive Languages Context-Free Languages

​

Regular Languages

Non-Recursively Enumerable Languages

Deterministic Finite State Automata (DFA)

TOC notes by S P CHARI

……..

ken into cells

ead.

One-way, infinite tape, bro One-way, read-only tape h Finite control, i.e.,

finite number of states, and

transition rules between them, i.e.,

a program, containing the position of the read head, current symbol being scanned, and the current “state.”

A string is placed on the tape, read head is positioned at the left end, and the DFA will read the string one symbol at a time until all symbols have been read. The DFA will then either accept or reject the string.

Finite Control

TOC notes by S P CHARI

The finite control can be described by a transition diagram or table:

Example #1:

1

q₀ q₀ q₁

1 1

q₀ q₀

One state is final/accepting, all others are rejecting.

The above DFA accepts those strings that contain an even number of 0’s, including the

null string, over Sigma = {0,1}

L = {all strings with zero or more 0’s}

Note, the DFA must reject all other strings

q₀

0 0

q₁

0

q₀

1

​

0

1

Note:

TOC notes by S P CHARI

• Machine is for accepting a language, language is the purpose!

​

• Many equivalent machines may accept the same language, but a machine cannot accept multiple languages!

L

• Id’s of the characters or states are irrelevant,

you can call them by any names!

Sigma = {0, 1} ≡ {a, b}

States = {q0, q1} ≡ {u, v}, as long as they have

identical (isomorphic) transition table

M1

M2

….

M-inf

An equivalent machine to the previous example (DFA for even number of 0’s):

TOC notes by S P CHARI

q₀ q₃ q₁ q₂ q₂ q₂

One state is final/accepting, all others are rejecting.

The above DFA accepts those strings that contain an even number of 0’s, including null

string, over Sigma = {0,1}

Can you draw a machine for a language by excluding the null string from the language? L =

{all strings with 2 or more 0’s}

q₀

1 0 0 1 1_q1

0

0

1

accept string

q₂

1

1

0

q₃

1

0

Example #2:

TOC notes by S P CHARI

a

c

c

c

b

accepted

q₀

q₀

q₁

q₂

q₂

q₂

a

a

c

rejected

q₀ q₀ q₀ q₁

​

Accepts those strings that contain at least two c’s

q₁

q₀

q₂

a

b

a

b

c

c

a/b/c

a/b/c

q₂

a q₀

a

q₁

b

b

c

c

Inductive Proof (sketch): that the machine correctly accepts strings with at least two c’s

Proof goes over the length of the string.

Base: x a string with |x|=0. state will be q0 => rejected.

Inductive hypothesis: |x|= integer k, & string x is rejected - in state q0 (x must have zero c),

OR, rejected – in state q1 (x must have one c),

OR, accepted – in state q2 (x has already with two c’s)

Inductive steps: Each case for symbol p, for string xp (|xp| = k+1), the last symbol p = a, b or c

Formal Definition of a DFA

TOC notes by S P CHARI

A DFA is a five-tuple:

M = (Q, Σ, δ, q₀, F)

Q Σ

q₀

F

δ

A finite set of states

A finite input alphabet

The initial/starting state, q₀ is in Q

A set of final/accepting states, which is a subset of Q

A transition function, which is a total function from Q x Σ to Q

δ: (Q x Σ) –> Q

δ(q,s) = q’

δ is defined for any q in Q and s in Σ, and

is equal to some state q’ in Q, could be q’=q

Intuitively, δ(q,s) is the state entered by M after reading symbol s while in state q.

Revisit example #1:

TOC notes by S P CHARI

Q = {q₀, q₁}

Σ = {0, 1}

Start state is q₀

F = {q₀}

δ:

0

q₁

1

q₀

q₀

q₁

q

0

q₁

0

0

1

1

Revisit example #2:

TOC notes by S P CHARI

Q = {q₀, q₁, q₂}

Σ = {a, b, c} Start state is q₀ F = {q₂}

δ:

a

q₀

b q₀

c

q₁

q₀

q₁

q₂

​

Since δ is a functio e option.

It follows that for a given string, there is exactly one computation.

q₁

q₀

q₂

a

b

a

b

c

c

a/b/c

Extension of δ to Strings

TOC notes by S P CHARI

δ^{^} : (Q x Σ^*) –> Q

δ^{^}(q,w) – The state entered after reading string w having started in state q.

​

Formally:

1. δ^{^}(q, ε) = q, and
2. For all w in Σ^* and a in Σ

δ^{^}(q,wa) = δ (δ^{^}(q,w), a)

Recall Example #1:

TOC notes by S P CHARI

δ^{^}(q₀, 011)

= δ (δ^{^}(q₀,01), 1)

= δ (δ ( δ^{^}(q₀,0), 1), 1)

= δ (δ (δ (δ^{^}(q₀, λ), 0), 1), 1)

= δ (δ (δ(q₀,0), 1), 1)

= δ (δ (q₁, 1), 1)

= δ (q₁, 1)

= q₁

by rule #2

by rule #2

by rule #2

by rule #1

by definition of δ by definition of δ by definition of δ

Is 011 accepted? No, since δ^{^}(q₀, 011) = q₁ is not a final state.

q₀

q₁

0

What is δ^{^}(q₀, 011)? Informally, it is the state entered by⁰ M after processing 011 having started in state q_0.

Formally:

1

1

Note that:

TOC notes by S P CHARI

δ^{^} (q,a) = δ(δ^{^}(q, ε), a)

= δ(q, a)

by definition of δ^{^}, rule #2

by definition of δ^{^}, rule #1

Therefore:

δ^{^} (q, a₁a₂…a_n) = δ(δ(…δ(δ(q, a1), a2)…), a_n)

However, we will abuse notations, and use δ in place of δ^{^}: δ^{^}(q, a₁a₂…a_n) = δ(q, a₁a₂…a_n)

Example #3:

TOC notes by S P CHARI

δ(q₀, 011)

= δ (δ(q₀,01), 1)

= δ (δ (δ(q₀,0), 1), 1)

= δ (δ (q₁, 1), 1)

= δ (q₁, 1)

= q₁

by rule #2

by rule #2

by definition of δ by definition of δ by definition of δ

Is 011 accepted? No, since δ(q₀, 011) = q₁ is not a final state.

Language?

L ={ all strings over {0,1} that has 2 or more 0 symbols}

q

q

⁰ 1

q

2

1

1

0

0

1

What is δ(q₀, 011)? Informally, it is the state entered by M after process0ing 011 having

started in state q_0.

Formally:

Recall Example #3:

TOC notes by S P CHARI

What is δ(q₁, 10)?

Is 10 accepted? No, since δ(q₀, 10) = q₁ is not a final state. The fact that δ(q₁, 10) = q₂ is

irrelevant, q1 is not the start state!

0

q

1

q

0

q

2

1

1

0

1

0

Definitions related to DFAs

Let M = (Q, Σ, δ,q₀,F) be a DFA and let w be in Σ^*. Then w is accepted by M iff δ(q₀,w) = p for some state p in F.

Let M = (Q, Σ, δ,q₀,F) be a DFA. Then the language accepted by M is the set:

L(M) = {w | w is in Σ^* and δ(q₀,w) is in F} Another equivalent definition:

L(M) = {w | w is in Σ^* and w is accepted by M}

Let L be a language. Then L is a regular language iff there exists a DFA M such that L = L(M).

Let M₁ = (Q₁, Σ₁, δ₁, q₀, F₁) and M₂ = (Q₂, Σ₂, δ₂, p₀, F₂) be DFAs. Then M₁ and M₂ are equivalent iff

L(M₁) = L(M₂).

TOC notes by S P CHARI

TOC notes by S P CHARI

Notes:

A DFA M = (Q, Σ, δ,q₀,F) partitions the set Σ^* into two sets: L(M) and

Σ^* - L(M).

If L = L(M) then L is a subset of L(M) and L(M) is a subset of L (def. of set equality). Similarly, if L(M₁) = L(M₂) then L(M₁) is a subset of L(M₂) and L(M₂) is a subset of L(M₁). Some languages are regular, others are not. For example, if

Regular: L₁ = {x | x is a string of 0's and 1's containing an even

number of 1's} and

Not-regular: L₂ = {x | x = 0ⁿ1ⁿ for some n >= 0}

Can you write a program to “simulate” a given DFA, or any arbitrary input DFA?

Question we will address later:

How do we determine whether or not a given language is regular?

Give a DFA M such that:

TOC notes by S P CHARI

L(M) = {x | x is a string of 0’s and 1’s and |x| >= 2}

Prove this by induction

q₁

q₀

q₂

0/1

0/1

0/1

Give a DFA M such that:

TOC notes by S P CHARI

L(M) = {x | x is a string of (zero or more) a’s, b’s and c’s such that x does not contain the substring aa}

Logic:

In Start state (q0): b’s and c’s: ignore – stay in same state

q0 is also “accept” state

First ‘a’ appears: get ready (q1) to reject

But followed by a ‘b’ or ‘c’: go back to start state q0

When second ‘a’ appears after the “ready” state: go to reject state q2 Ignore everything after getting to the “reject” state q2

a

a/b/c

a

q₀ q₁ q₂

b/c

b/c

Give a DFA M such that:

TOC notes by S P CHARI

L(M) = {x | x is a string of a’s, b’s and c’s such that x contains the substring aba}

a

a/b/c

b

q₀ q₁

c

Logic: acceptance is straight forward, progressing on each expected symbol

However, rejection needs special ca_bre_/c, in each state (for DFA, we will see this becomes

easier in NFA, non-deterministic machine)

q₂ q₃

b/c

a

a

Give a DFA M such that:

TOC notes by S P CHARI

q₀

b

q₇

Remember, you may hav_qe multiple “final” sta_qtes, but only one “st_qart” state

4 5 6

b

b

b

a

q₂

q₁

q₃

a

L(M) = {x | x is a string of a’s and b’s such that x

contains both aa and bb}

First do, for a language where ‘aa’ comes before ‘bb’

Then do its reverse; and then parallelize them.

a

a

b

a/b

b

a

a

a

b

TOC notes by S P CHARI

Let Σ = {0, 1}. Give DFAs for {}, {ε}, Σ^*, and Σ⁺.

For {}: For {ε}:

For Σ^*:

For Σ⁺:

0/1

q₀

0/1

q₀

q₁

q₀

0/1

0/1

0/1

q₀

q₁

0/1

Problem: Third symbol from last is 1

TOC notes by S P CHARI

0/1

q₁

q₀

q₃

1

0/1

q₂

0/1

Is this a DFA?

​

​

No, but it is a Non-deterministic Finite Automaton

Nondeterministic Finite State Automata (NFA)

TOC notes by S P CHARI

An NFA is a five-tuple:

M = (Q, Σ, δ, q₀, F)

Q Σ

q₀

F

δ

A finite set of states

A finite input alphabet

The initial/starting state, q₀ is in Q

A set of final/accepting states, which is a subset of Q

A transition function, which is a total function from Q x Σ to 2^Q

δ: (Q x Σ) –> 2^Q :2^Q is the power set of Q, the set of all subsets of Q

:The set of all states p such that there is a transition

labeled s from q to p

δ(q,s)

δ(q,s) is a function from Q x S to 2^Q (but not only to Q)

TOC notes by S P CHARI

Example #1: one or more 0’s followed by one or more 1’s

Q = {q₀, q₁, q₂}

Σ = {0, 1}

Start state is q₀

F = {q₂}

δ:

0

1

q₀

q

q

q₁

q₀

q₂

0

1

0

1

0/1

Example #2: pair of 0’s or pair of 1’s as substring

Q = {q₀, q₁, q₂ , q₃ , q₄}

Σ = {0, 1}

Start state is q₀

F = {q₂, q₄}

δ: 0

1

q₀

q₁

q₂ q₃ q₄

q₀

0/1

0

0

q₃

q₄

0/1

q₁

q₂

0/1

Joshi

1

1

Notes:

TOC notes by S P CHARI

δ(q,s) may not be defined for some q and s (what does that mean?) δ(q,s) may map to multiple q’s

A string is said to be accepted if there exists a path from q₀ to some state in F

A string is rejected if there exist NO path to any state in F

The language accepted by an NFA is the set of all accepted strings

Question: How does an NFA find the correct/accepting path for a given string?

NFAs are a non-intuitive computing model

You may use backtracking to find if there exists a path to a final state (following slide)

Why NFA?

We are primarily interested in NFAs as language defining capability, i.e., do NFAs accept languages that

DFAs do not?

Other secondary questions include practical ones such as whether or not NFA is easier to develop, or how does one implement NFA

Determining if a given NFA (example #2) accepts a given string (001) can be done

algorithmically:

TOC notes by S P CHARI

q₀

q₀

q₀

q₃

q₃

q₄ q₄

Each level will have at most n states:

Complexity: O(|x|*n), for running over a string x

accepted

₁q₀

q₁

0

0

q₀

0/1

0

q₃

1

1

q₂

q₁

0

0/1

q₄

0/1

Another example (010):

TOC notes by S P CHARI

q₀

q₀

q₀

q₀

q₃

q₁

q₃

not accepted

All paths have been explored, and none lead to an accepting state.

0

1

0

q₀

0/1

0

q₃

q₄

1

1

q₂

q₁

0

Question: Why non-determinism is useful?

TOC notes by S P CHARI

Non-determinism = Backtracking Compressed information

Non-determinism hides backtracking

Programming languages, e.g., Prolog, hides backtracking => Easy to program at a higher level: what we

want to do, rather than how to do it

Useful in algorithm complexity study

Is NDA more “powerful” than DFA, i.e., accepts type of languages that any DFA cannot?

TOC notes by S P CHARI

Let Σ = {a, b, c}. Give an NFA M that accepts:

L = {x | x is in Σ^* and x contains ab}

Is L a subset of L(M)? Or, does M accepts all string in L?

Is L(M) a subset of L? Or, does M rejects all strings not in L?

Is an NFA necessary? Can you draw a DFA for this L?

Designing NFAs is not as trivial as it seems: easy to create bug accepting string outside

language

^q₀ q₁

q₂

a

a/b/c

b

a/b/c

TOC notes by S P CHARI

Let Σ = {a, b}. Give an NFA M that accepts:

L = {x | x is in Σ^* and the third to the last symbol in x is b}

​

​

a/b

Is L a subset of L(M)?

Is L(M) a subset of L?

Give an equivalent DFA as an exercise.

q₁

q₀

b

q₃

a/b

q₂

a/b

Extension of δ to Strings and Sets of States

What we currently have:

δ : (Q x Σ) –> 2^Q

q₀

0

1

q₁

q₄

0

1

q₂

0

0

1

What we want (why?): δ : (2^Q x Σ^*) –> 2^Q

We will do this in two steps, which will be slightly different from the book, and we will make use of the following NFA.

0

q₃

​

TOC notes by S P CHARI

0

Extension of δ to Strings and Sets of States

TOC notes by S P CHARI

Step #1:

Given δ: (Q x Σ) –> 2^Q define δ^#: (2^Q x Σ) –> 2^Q as follows:

for all subsets R of Q, and symbols a in Σ

Note that:

1) δ^#(R, a) = δ(q, a)

∪

q∈R

δ^#({p},a) = δ(q, a)

= δ(p, a)

by definition of δ^#, rule #1 above

∪

q∈{ p}

Hence, we can use δ for δ^#

δ({q₀, q₂}, 0)

δ({q₀, q₁, q₂}, 0)

These now make sense, but previously they did not.

Example:

TOC notes by S P CHARI

δ({q₀, q₂}, 0)

= δ(q₀, 0) U δ(q₂, 0)

= {q₁, q₃} U {q₃, q₄}

= {q₁, q₃, q₄}

δ({q₀, q₁, q₂}, 1) = δ(q₀, 1) U δ(q₁, 1) U δ(q₂, 1)

= {} U {q₂, q₃} U {}

= {q₂, q₃}

Step #2:

TOC notes by S P CHARI

Given δ: (2^Q x Σ) –> 2^Q define δ^{^}: (2^Q x Σ*) –> 2^Q as follows:

δ^{^}(R,w) – The set of states M could be in after processing string w, having started from any

state in R.

Formally:

2. δ^{^}(R, ε) = R
3. δ^{^}(R,wa) = δ (δ^{^}(R,w), a)

for any subset R of Q

for any w in Σ^*, a in Σ, and

subset R of Q

Note that:

δ^{^}(R, a)

= δ(δ^{^}(R, ε), a)

= δ(R, a)

by definition of δ^{^}, rule #3 above by definition of δ^{^}, rule #2 above

Hence, we can use δ for δ^{^}

δ({q₀, q₂}, 0110)

δ({q₀, q₁, q₂}, 101101)

These now make sense, but previously they did not.

TOC notes by S P CHARI

Example:

What is δ({q₀}, 10)?

Informally: The set of states the NFA could be in after processing 10,

having started in state q₀, i.e., {q₁, q₂, q₃}.

Formally:

δ({q₀}, 10) = δ(δ({q₀}, 1), 0)

= δ({q₀}, 0)

= {q₁, q₂, q₃}

Is 10 accepted? Yes!

q₀

0

1

q₁

q₃

0

1

q₂

1

1

0

Example:

TOC notes by S P CHARI

What is δ({q₀, q₁}, 1)?

δ({q₀ , q₁}, 1)

= δ({q₀}, 1) ∪ δ({q₁}, 1)

= {q₀} ∪ {q₂, q₃}

= {q₀, q₂, q₃}

What is δ({q₀, q₂}, 10)?

δ({q₀ , q₂}, 10)

= δ(δ({q₀ , q₂}, 1), 0)

= δ(δ({q₀}, 1) U δ({q₂}, 1), 0)

= δ({q₀} ∪ {q₃}, 0)

= δ({q₀,q₃}, 0)

= δ({q₀}, 0) ∪ δ({q₃}, 0)

= {q₁, q₂, q₃} ∪ {}

= {q₁, q₂, q₃}

Example:

TOC notes by S P CHARI

δ({q₀}, 101)

= δ(δ({q₀}, 10), 1)

= δ(δ(δ({q₀}, 1), 0), 1)

= δ(δ({q₀}, 0), 1)

= δ({q₁ , q₂, q₃}, 1)

= δ({q₁}, 1) U δ({q₂}, 1) U δ({q₃}, 1)

= {q₂, q₃} U {q₃} U {}

= {q₂, q₃}

Is 101 accepted? Yes! q₃ is a final state.

Definitions for NFAs

TOC notes by S P CHARI

Let M = (Q, Σ, δ,q₀,F) be an NFA and let w be in Σ^*. Then w is accepted by M iff δ({q₀}, w)

contains at least one state in F.

Let M = (Q, Σ, δ,q₀,F) be an NFA. Then the language accepted by M is the set: L(M) = {w | w is in Σ^* and δ({q₀},w) contains at least one state in F}

Another equivalent definition:

L(M) = {w | w is in Σ^* and w is accepted by M}

Equivalence of DFAs and NFAs

TOC notes by S P CHARI

Do DFAs and NFAs accept the same class of languages?

Is there a language L that is accepted by a DFA, but not by any NFA? Is there a language L that is accepted by an NFA, but not by any DFA?

​

Observation: Every DFA is an NFA, DFA is only restricted NFA.

Therefore, if L is a regular language then there exists an NFA M such that L = L(M). It follows that NFAs accept all regular languages.

But do NFAs accept more?

TOC notes by S P CHARI

Consider the following DFA: 2 or more c’s

Q = {q₀, q₁, q₂}

Σ = {a, b, c} Start state is q₀ F = {q₂}

δ:

a

q₀

b q₀

c

q₁

q₀

q₁

q₂

q₁

q₀

q₂

a

b

a

b

c

c

a/b/c

An Equivalent NFA:

TOC notes by S P CHARI

Q = {q₀, q₁, q₂}

Σ = {a, b, c} Start state is q₀ F = {q₂}

δ:

q₀

q₁

q₂

q₁

q₀

q₂

a

b

a

b

c

c

a/b/c

TOC notes by S P CHARI

Lemma 1: Let M be an DFA. Then there exists a NFA M’ such that L(M) = L(M’).

Proof: Every DFA is an NFA. Hence, if we let M’ = M, then it follows that L(M’) = L(M). The above is just a formal statement of the observation from the previous slide.

TOC notes by S P CHARI

Lemma 2: Let M be an NFA. Then there exists a DFA M’ such that L(M) = L(M’).

Proof: (sketch)

Let M = (Q, Σ, δ,q₀,F).

Define a DFA M’ = (Q’, Σ, δ’,q^’₀,F’) as:

Q’ = 2^Q

= {Q₀, Q₁,…,}

Each state in M’ corresponds to a

subset of states from M

where Q_u = [q_i0, q_i1,…q_ij]

F’ = {Q_u | Q_u contains at least one state in F} q^’₀ = [q₀]

δ’(Q_u, a) = Q_v iff δ(Q_u, a) = Q_v

TOC notes by S P CHARI

Example: empty string or start and end with 0

Q = {q₀, q₁}

Σ = {0, 1}

Start state is q₀

F = {q₀}

δ:

0

1

q₀

q

q₁

q₀

0

0/1

0

Example of creating a DFA out of an NFA (as per the constructive proof):

TOC notes by S P CHARI

δ for DFA:

0

->q₀

1

q₁

q₀ ^-->q₀

q₁

0/1

0

0

^[q1^]{q₁^}

[ ] ^{write as} [q₁]

{}

write as [ ]

TOC notes by S P CHARI

δ:

0

1

->q₀

[q₁ [ ]

[q₀₁

q₁

q₀

Example of creating a DFA out of an NFA (as per the constructive proof):

0/1

0

0

TOC notes by S P CHARI

δ:

0

1

->q₀

[q₁ [ ]

[q₀₁

q₁

q₀

Example of creating a DFA out of an NFA (as per the constructive proof):

0/1

0

0

TOC notes by S P CHARI

δ:

0

1

->q₀

[q₁ [ ]

[q₀₁

q₁

q₀

Example of creating a DFA out of an NFA (as per the constructive proof):

0/1

0

0

TOC notes by S P CHARI

Construct DFA M’ as follows:

δ({q₀}, 0) = {q₁}

δ({q₀}, 1) = {}

δ({q₁}, 0) = {q₀, q₁} =>

δ({q₁}, 1) = {q₁}

δ({q₀, q₁}, 0) = {q₀, q₁}

δ({q₀, q₁}, 1) = {q₁} =>

δ({}, 0) = {}

δ({}, 1) = {}

=> δ’([q₀], 0) = [q₁]

=> δ’([q₀], 1) = [ ]

δ’([q₁], 0) = [q₀q₁]

=> δ’([q₁], 1) = [q₁]

=> δ’([q₀q₁], 0) = [q₀q₁]

δ’([q₀q₁], 1) = [q₁]

=>

=>

δ’([ ], 0) = [ ]

δ’([ ], 1) = [ ]

[ ]

1

0

1

[q₁]

0/1

[q₀]

0

1

[q₀q₁]

0

TOC notes by S P CHARI

Theorem: Let L be a language. Then there exists an DFA M such that L = L(M) iff there

exists an NFA M’ such that L = L(M’).

Proof:

(if) Suppose there exists an NFA M’ such that L = L(M’). Then by Lemma 2 there

exists an DFA M such that L = L(M).

(only if) Suppose there exists an DFA M such that L = L(M). Then by Lemma 1

there exists an NFA M’ such that L = L(M’).

Corollary: The NFAs define the regular languages.

TOC notes by S P CHARI

Note: Suppose R = {}

δ(R, 0)

= δ(δ(R, ε), 0)

= δ(R, 0)

= δ(q, 0)

= _∪{}

q∈R

Since R = {}

Exercise - Convert the following NFA to a DFA:

Q = {q₀, q₁, q₂}

Σ = {0, 1}

Start state is q₀

F = {q₀}

δ: 0

q₀

1

q₁

q

2

Problem: Third symbol from last is 1

TOC notes by S P CHARI

0/1

q₁

q₀

q₃

1

0/1

q₂

0/1

Now, can you convert this NFA to a DFA?

NFAs with ε Moves

TOC notes by S P CHARI

An NFA-ε is a five-tuple:

M = (Q, Σ, δ, q₀, F)

Q Σ

q₀

F

δ

A finite set of states

A finite input alphabet

The initial/starting state, q₀ is in Q

A set of final/accepting states, which is a subset of Q

A transition function, which is a total function from Q x Σ U {ε} to 2^Q

δ: (Q x (Σ U {ε})) –> 2^Q

δ(q,s)

-The set of all states p such that there is a transition labeled a from q to p, where a is in Σ U {ε}

Sometimes referred to as an NFA-ε other times, simply as an NFA.

Example:

TOC notes by S P CHARI

δ:

0

1

ε

q₀

- A string w = w₁w₂…w_n is processed

as w = ε^*w₁ε^*w₂ε^* … ε^*w_nε^*

q

q

Example: all computations on 00:

0 ε 0

q₀ q₀ q₁ q₂

:

q

q₀

ε

0/1

q₂

1

0

q₁

0

q₃

ε

0

1

Informal Definitions

Let M = (Q, Σ, δ,q₀,F) be an NFA-ε.

A String w in Σ^* is accepted by M iff there exists a path in M from q₀ to a state in F labeled by w and zero or more ε transitions.

The language accepted by M is the set of all strings from Σ^* that are accepted by M.

TOC notes by S P CHARI

ε-closure

TOC notes by S P CHARI

Define ε-closure(q) to denote the set of all states reachable from q by zero or more ε transitions.

Examples: (for the previous NFA)

ε-closure(q₀) = {q₀, q₁, q₂}

ε-closure(q₁) = {q₁, q₂}

ε-closure(q₂) = {q₂}

ε-closure(q₃) = {q₃}

ε-closure(q) can be extended to sets of states by defining:

ε-closure(P) = ε-closure(q)

Examples:

1 2 1 2

ε-closure({q , q }) = {q , q }

ε-closure({q₀, q₃}) = {q₀, q₁, q₂, q₃}

∪

q∈P

q₀

0/1

q₂

ε

1

0

q₁

0

q₃

ε

0

1

Extension of δ to Strings and Sets of States

TOC notes by S P CHARI

What we currently have:

δ : (Q x (Σ U {ε})) –> 2^Q

What we want (why?): δ : (2^Q x Σ^*) –> 2^Q

As before, we will do this in two steps, which will be slightly different from the book, and we will make use of the following NFA.

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

TOC notes by S P CHARI

Step #1:

Given δ: (Q x (Σ U {ε})) –> 2^Q define δ^#: (2^Q x (Σ U {ε})) –> 2^Q as follows:

1) δ^#(R, a) = δ(q, a) for all subsets R of Q, and symbols a in Σ U {ε}

Note that:

∪

q∈R

​

δ^#({p},a) = δ(q, a) by definition of δ^#, rule #1 above

= δ(p, a)

Hence, we can use δ for δ

#

δ({q₀, q₂}, 0)

δ({q₀, q₁, q₂}, 0)

These now make sense, but previously

they did not.

∪

q∈{ p}

Examples:

TOC notes by S P CHARI

What is δ({q₀ , q₁, q₂}, 1)?

δ({q₀ , q₁, q₂}, 1) = δ(q₀, 1) U δ(q₁, 1) U δ(q₂, 1)

= { } U {q₀, q₃} U {q₂}

= {q₀, q₂, q₃}

​

What is δ({q₀, q₁}, 0)?

δ({q₀ , q₁}, 0)

= δ(q₀, 0) U δ(q₁, 0)

= {q₀} U {q₁, q₂}

= {q₀, q₁, q₂}

Step #2:

TOC notes by S P CHARI

Given δ: (2^Q x (Σ U {ε})) –> 2^Q define δ^{^}: (2^Q x Σ^*) –> 2^Q as follows:

δ^{^}(R,w) – The set of states M could be in after processing string w, having starting

from any state in R.

Formally:

2) δ^{^}(R, ε) = ε-closure(R) - for any subset R of Q

3) δ^{^}(R,wa) = ε-closure(δ(δ^{^}(R,w), a))

- for any w in Σ^*, a in Σ, and subset R of Q

Can we use δ for δ^{^}?

TOC notes by S P CHARI

Consider the following example:

δ({q₀}, 0) = {q₀}

δ^{^}({q₀}, 0) = ε-closure(δ(δ^{^}({q₀}, ε), 0))

= ε-closure(δ(ε-closure({q₀}), 0))

= ε-closure(δ({q_0, q₁, q₂}, 0))

= ε-closure(δ(q₀, 0) U δ(q₁, 0) U δ(q₂, 0))

= ε-closure({q₀} U {q₁, q₂} U {q₂})

By rule #3

By rule #2

By ε-closure

By rule #1

= ε-closure({q₀, q₁, q₂})

= ε-closure({q₀}) U ε-closure({q₁}) U ε-closure({q₂})

= {q₀, q₁, q₂} U {q₁, q₂} U {q₂}

= {q₀, q₁, q₂}

So what is the difference?

δ(q₀, 0) - Processes 0 as a single symbol, without ε transitions.

δ^{^}(q₀ , 0) - Processes 0 using as many ε transitions as are possible.

Example:

TOC notes by S P CHARI

δ^{^}({q₀}, 01) = ε-closure(δ(δ^{^}({q₀}, 0), 1))

= ε-closure(δ({q₀, q₁, q₂}), 1)

= ε-closure(δ(q₀, 1) U δ(q₁, 1) U δ(q₂, 1))

= ε-closure({ } U {q₀, q₃} U {q₂})

= ε-closure({q₀, q₂, q₃})

By rule #3 Previous slide

By rule #1

= ε-closure({q₀}) U ε-closure({q₂}) U ε-closure({q₃})

= {q₀, q₁, q₂} U {q₂} U {q₃}

= {q₀, q₁, q₂, q₃}

Definitions for NFA-ε Machines

Let M = (Q, Σ, δ,q₀,F) be an NFA-ε and let w be in Σ^*. Then w is accepted by M iff δ^{^}({q₀},

w) contains at least one state in F.

Let M = (Q, Σ, δ,q₀,F) be an NFA-ε. Then the language accepted by M is the set: L(M) = {w | w is in Σ^* and δ^{^}({q₀},w) contains at least one state in F}

Another equivalent definition:

L(M) = {w | w is in Σ^* and w is accepted by M}

TOC notes by S P CHARI

Equivalence of NFAs and NFA-εs

TOC notes by S P CHARI

Do NFAs and NFA-ε machines accept the same class of languages?

Is there a language L that is accepted by a NFA, but not by any NFA-ε? Is there a language L that is accepted by an NFA-ε, but not by any DFA?

​

Observation: Every NFA is an NFA-ε.

Therefore, if L is a regular language then there exists an NFA-ε M such that L = L(M). It follows that NFA-ε machines accept all regular languages.

But do NFA-ε machines accept more?

TOC notes by S P CHARI

Lemma 1: Let M be an NFA. Then there exists a NFA-ε M’ such that L(M) = L(M’).

Proof: Every NFA is an NFA-ε. Hence, if we let M’ = M, then it follows that L(M’) = L(M).

The above is just a formal statement of the observation from the previous slide.

Lemma 2: Let M be an NFA-ε. Then there exists a NFA M’ such that L(M) = L(M’).

TOC notes by S P CHARI

Proof: (sketch)

Let M = (Q, Σ, δ,q₀,F) be an NFA-ε. Define an NFA M’ = (Q, Σ, δ’,q₀,F’) as:

F’ = F U {q} if ε-closure(q) contains at least one state from F

F’ = F otherwise

δ’(q, a) = δ^{^}(q, a) - for all q in Q and a in Σ

Notes:

δ’: (Q x Σ) –> 2^Q is a function

M’ has the same state set, the same alphabet, and the same start state as M

M’ has no ε transitions

Example:

TOC notes by S P CHARI

Step #1:

Same state set as M

q₀ is the starting state

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

Example:

TOC notes by S P CHARI

Step #2:

q₀ becomes a final state

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

Example:

TOC notes by S P CHARI

Step #3:

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

0

0

0

Example:

TOC notes by S P CHARI

Step #4:

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

0/1

0/1

0/1

1

Example:

TOC notes by S P CHARI

Step #5:

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

0/1

0/1

0/1

1

0

0

Example:

TOC notes by S P CHARI

Step #6:

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

0/1

0/1

1

0/1

0/1

0/1

1

1

Example:

TOC notes by S P CHARI

Step #7:

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₃

q₀

0/1

0/1

1

0/1

0/1

0/1

1

1

0

q₁

Example:

TOC notes by S P CHARI

Step #8:

Done!

[use table of e-closure]

q₀

ε

0/1

q₂

1

0

q₁

0

ε

0

q₃

1

q₂

q₁

q₃

q₀

0/1

0/1

1

0/1

0/1

0/1

1

1

0/1

TOC notes by S P CHARI

Theorem: Let L be a language. Then there exists an NFA M such that L= L(M) iff there

exists an NFA-ε M’ such that L = L(M’).

Proof:

(if) Suppose there exists an NFA-ε M’ such that L = L(M’). Then by Lemma 2

there exists an NFA M such that L = L(M).

(only if) Suppose there exists an NFA M such that L = L(M). Then by Lemma 1

there exists an NFA-ε M’ such that L = L(M’).

Corollary: The NFA-ε machines define the regular languages.

UNIT-2�REGULAR EXPRESSIONS

TOC notes by S P CHARI

Introduction

TOC notes by S P CHARI

• The Language accepted by finite automata are easily described by simple expressions called regular expressions.

​

• The regular expression is the most effective way to represent any language.

​

• The language accepted by some regular expression is known as a regular language.

Regular Expressions

TOC notes by S P CHARI

1. Any terminal symbol(i.e. an element of ∑), Ꜫ and φ are regular expressions.
2. The union of two regular expressions R₁ and R₂, written as R₁+R₂, is also a regular expression.
3. The concatenation of two regular expressions R₁ and R₂, written as R₁R₂, is also a regular expression.
4. The iteration(or Closure) of a regular expression R, written as R* is also a regular expression.
5. If R is a regular expression , then (R) is also a regular expression.

Regular Expressions

Identity Rules :

Let P,Q and R are the regular expressions then the identity rules are as follows:

1. φ +R = R
2. φR = Rφ = φ
3. ꜪR = RꜪ = R
4. Ꜫ* = Ꜫ and φ *= Ꜫ
5. R + R = R
6. R*R* = R*
7. RR* = R*R
8. (R*)*=R*
9. Ꜫ + RR*= R* = Ꜫ +R*R
10. (PQ)*P = P(QP)*
11. (P+Q)* = (P*Q*)* = (P*_TOC+_noQ_{tes b}*_y )_{Pallavi Joshi}
12. (P+Q)R = PR + QR and R(P+Q) = RP + RQ

Regular Expressions

TOC notes by S P CHARI

• Exercise 2: Construct the regular expression for the language which accepts all the strings which begin or end with either 00 or 11.

Solution:

The R.E. can be categorized into two subparts.

R = L1 + L2

L1 = The String which begin with 00 or 11. L2 = The String which end with 00 or 11.

Let us find out L1 and L2.

L1 = (00+11)( any number of 0’s and 1’s ) L1 = (00+11)(0+1)*

L2 = ( any number of 0’s and 1’s ) (00+11) L2 = (0+1)*(00+11)

Hence

R = [(00+11)(0+1)*] + [(0+1)*(00+11)]

Algorithm to build R.E. from given DFA

TOC notes by S P CHARI

1. Let q₁ be the initial state.
2. There are q₂,q₃,q₄,….q_n number of states. The final state may be some q_j where j<=n.
3. Let α_ji represents the transition from qj to qi.
4. Calculate qi such that q_i = α_ji .q_j

If qi is a start state

q_i = α_ji .q_j +Ꜫ

5. Similarly compute the final state which ultimately gives the regular expression r.

Regular Expressions

TOC notes by S P CHARI

• Exercise 1: Write a regular expression for the set of strings that contains an even number of 1’s over ∑={0,1}. Treat zero 1’s as an even number.

Solution:

Q0

Q1

1

0

0

1

The regular expression for the above F.A. is 0*10*1

DFA to RE via State

TOC notes by S P CHARI

1^E.^limStaⁱrⁿti^ang^tiowiⁿth ⁽¹int⁾ermediate states and then moving to accepting states, apply the state elimination process to produce an equivalent automaton with regular expression labels on the edges.

• The result will be a one or two state automaton with a start state and

accepting state.

DFA to RE State

TOC notes by S P CHARI

^Elimin2^a. ^tiI^of tⁿhe⁽t²w⁾o states are different, we will have an automaton that looks like the following:

Start

S

R

T

We can describe this automaton as: (R+SU*T)*SU*

U

DFA to RE State

TOC notes by S P CHARI

^Elimin3^a. ^tIf^iothⁿe s⁽t³ar⁾t state is also an accepting state, then we must also perform a state elimination from the original automaton that gets rid of every state but the start state. This leaves the following:

R

Start

​

​

We can describe this automaton as simply R*.

DFA to RE State Elimination (4)

TOC notes by S P CHARI

4. If there are n accepting states, we must repeat the above steps for each accepting states to get n different regular expressions, R₁, R₂,

… R_n.

5. For each

repeat we turn any other accepting state to non-

accepting.

6. The desired regular expression for the automaton is then the union of each of

the n regular expressions: R₁∪ R₂… ∪ R_N

DFA🡪RE Example

TOC notes by S P CHARI

• Convert the following to a RE

• First convert the edges to RE’s:

0

3

Start

1

2

1

1

0

0

0,1

3

Start

1

2

1

1

0

0+1

DFA 🡪 RE Example (2)

TOC notes by S P CHARI

• Eliminate State 1:

• To:

Start

0

0

3

1

2

1

1

0+1

3

Start

2

11

0+10

0+1

Note edge from 3🡪3

Answer: (0+10)*11(0+1)*

Second Example

TOC notes by S P CHARI

• Automata that accepts even number of 1’s

• Eliminate state 2:

1

Start

2

3

1

1

0

1

0 0

0+10*1

1

Start

3

0

10*1

Second Example (2)

• Two accepting states, turn off state 3 first

Start

1 3

0

0+10*1

10*1

0

0+10*1

10*1

3

1

Start

This is just 0*; can ignore_Tg_Oo_C i_nn_otg_est_bo_{y P}s_at_la_lat_ve_{i Jo}3_shs_i ince we would “die”

Second Example (3)

• Turn off state 1 second:

1

Start

3

0

0+10*1

10*1

This is just 0*10*1(0+10*1)*

Combine from previous slide to get

0* + 0*10*1(0+10*1)*

0+10*1

1

Start

3

0

10*1

TOC notes by S P CHARI

Converting a RE to an Automata

TOC notes by S P CHARI

• We have shown we can convert an automata to a RE. To show equivalence we must also go the other direction, convert a RE to an automaton.
• We can do this easiest by converting a RE to an ε-NFA

RE to ε-NFA

TOC notes by S P CHARI

• Basis:

R=a

R=ε

ε

R=Ø

a

Next slide: More complex RE’s

TOC notes by S P CHARI

R=S+T

S

T

ε

ε

ε

ε

R=ST

S

T

ε

R=S^*

ε

S

ε

ε

ε

RE to ε-NFA Example

TOC notes by S P CHARI

• Convert R= (ab+a)* to an NFA
• We proceed in stages, starting from simple elements and working our way up

a

a

b

b

ab

a

b

ε

RE to ε-NFA Example (2)

ab+a

(ab+a)*

a

b

ε

a

ε

ε

ε

ε

a

b

ε

a

ε

ε

ε

ε

ε

ε

ε

ε

TOC notes by S P CHARI

CONTEXT FREE GRAMMAR

TOC notes by S P CHARI

Prerequisite

TOC notes by S P CHARI

1. At very first session we have seen that the Finite Automata and importance of Finite State Machines and the construction of Deterministic Finite Automata and some examples on it.
2. In previous session we have seen that the construction of Regular Expressions for the given problems and how to generate a Regular expression from the DFA and vice versa.
3. The above two concepts are required to understand the Context Free Grammar and the applications of CFG.

TOC notes by S P CHARI

DEFINITION

​

• The Context Free Grammar can be defined as a set denoted by G=(V,T,P,S) Where

V- set of non-terminals Ex: { P,Q,R…} T- set of Terminals Ex: {p,q,r …}

P- set of Production rules

Where non-terminal -> non-terminal

non-terminal -> terminal

S- is start symbol.

• G=({S},{0,1},P,S)

Where P = { S->0S

TOC notes by S P CHARI

EXAMPLE

S->1S S->Ꜫ }

TOC notes by S P CHARI

Example1 : Construct CFG which consists of all the strings having atleast one occurrence of ‘000’ over input {0,1}.

• Solution:

We need to construct the equivalent R.E for the given problem

first.

The R.E=(any number of 0’s or 1’s) 000 (any number of 0’s or 1’s)

Thus R.E = (0+1)*000(0+1)*

​

Now let us build the production rules to satisfy the above R.E

{ S->ATA

A->0A|1A|Ꜫ T->000 }

Excercise1: Find the CFG for the odd length of strings in{a,b}* with middle symbol a

Excercise2: Generate the a CFG to obtain balanced set of parenthesis(i.e. every left parenthesis should match with corresponding right parenthesis)

TOC notes by S P CHARI

Derivation Trees

TOC notes by S P CHARI

• Definition: Derivation tree is a graphical representation for the derivation of the given production rules for a given CFG.
• It is the simple way to show how the derivation can be done to obtain some string from given set of production rules.
• The derivation tree is also called as Parse tree. Properties of Derivation Tree:-
• The root node is always a node indicating start symbol.
• The derivation is read from left to right.
• The leaf nodes are always terminal nodes.
• The interior nodes are always the non-terminal nodes.

Example2: The CFG is given as S->bSb | a | b is a production rule. The S is a start symbol.

TOC notes by S P CHARI

• Solution :

The Derivation tree for deriving a string bbabb as follows.

S

​

b S b

b S b a

By Simply reading the leaf nodes we can obtain the desired string.

TOC notes by S P CHARI

Exercise : Construct the derivation tree for the string ‘aabbabba’ from the CFG given by

S->aB|bA

A->a|aS|bAA B->b|bS|aBB

Difference between Regular Grammar and

Context Free Gram

mar

MINIMIZATION OF CFG

TOC notes by S P CHARI

• The properties of reduced grammar are as follows.
• Each variable(i.e. non terminal) and each terminal of G appears in the derivation of some word in L.
• There should not be any production as X->Y where X and Y are non terminal.
• If Ꜫ is not in the language L then there need not be the production X-> Ꜫ.

The Reduction of Grammar as follows

TOC notes by S P CHARI

Removal of Useless

symbols

Elimination of

Ꜫ Productions

Removal of unit

production

Removal of useless symbols

TOC notes by S P CHARI

• Any symbol is not useful when it appears on R.H.S. in the production rule. If no

such derivation exists then it is supposed to be a useless symbol.

For Example:

G= (V,T,P,S) where V={S,T,X} T={0,1} S->0T|1T|X|0|1

T->00

In the above grammar S->X there is no further rule as a definition to X. Hence we can declare X is a useless symbol. Therefore we can remove the S-> X production from the given grammar.

After removal of useless symbol form the given grammar the Grammar should be as follows.

G= (V,T,P,S) where V={S,T} T={0,1}

S->0T|1T|0|1

T->00

Elimination of Ꜫ production

TOC notes by S P CHARI

• In CFG if there is Ꜫ production we can remove it ,without changing the meaning of the grammar.

Example:

S->0S|1S| Ꜫ

from the above Grammar we can remove Ꜫ production without changing the meaning of it.

Simply if we place S-> Ꜫ in other rules.

we get S->0 and S->1 Hence we can rewrite the productions as follows

S->0S|1S|0|1

Thus we can remove Ꜫ production from the given grammar

Example2: For the CFG given below remove Ꜫ production S->aSa

S->bSb

S-> Ꜫ

• Solution:

According to the replacement procedure we will place Ꜫ at S in the sentential form.

S->aSa if S= Ꜫ S->aa

Similarly if

S->bSb if S= Ꜫ S->bb

Thus finally rules are

S->aSa|bSb|aa|bb

Thus we can remove Ꜫ prod^TOu^{C n}c^ott^esio^by n^Pallaf^vr^{i J}o^osm^hi the given grammar.

Excercise1: Eliminate Ꜫ productions from the CFG given below A->0B1|1B1

B->0B|1B|Ꜫ

TOC notes by S P CHARI

Exercise 2: Construct the CFG without Ꜫ productions form the given Grammar.

S->a|Ab|aBa A->b|Ꜫ

B->b|A

Removal of Unit Productions

S->0A|1B|01

• The unit productions are the productions in which one non terminal gives another non terminal.

For example X->Y, Y->Z, Z->X are the unit productions.

Example 1: if CFG is as below

S->0A|1B|C A->0S|00

B->1|A

C->01 then remove the unit productions.

Solution:

Clearly S->C is a unit production. But while removing it we have to consider what C gives. So, we add a rule to S.

TOC notes by S P CHARI

Example 1(2):

TOC notes by S P CHARI

• Similarly B->A is also unit production so we can modify it as

B->1|0S|00

Thus finally we can write CFG without unit productions as

S->0A|1B|01

A->0S|00

B->1|0S|00

C->01

TOC notes by S P CHARI

Exercise: Eliminate the unit productions fro the Grammar S->AB

A->a

B->C|b C->D

D->E|bC

E->d|Ab

Solution:

Thus the R.E = (a+b)ⁿ a (a+b)ⁿ Where n>=0

As the above given expression doesn’t represent regular language, The DFA can

not be designed for representing such language.

The CFG G= (V,T,P,S)

Where

V={S} T={a,b}

P={ S->aSa|bSb|aSb|bSa|a} S is Start Symbol.

Back

a or b

a or b

a

Length n

Length n

TOC notes by S P CHARI

Solution:

TOC notes by S P CHARI

Back

The well formed parenthesis means whenever opening parentheses is present there should be a closing parentheses associated with it.

Any expression must begin with opening bracket .We will consider T={(,[,),]} as set of brackets.

The CFG G=(V,T,P,S)

Where

V={S} T={(,[,),]}

P={ S->SS|()|[]|(S)|[S]

Where S is Start Symbol.

Solution :

TOC notes by S P CHARI

• To draw a tree we will first try to

obtain derivation for the string aabbabba.

S

aB

a aBB aa bS B

aab bA B aabba B aabba bS aabbab bA aabbabba

S->aB B->aBB B->bS S->bA A->a

B->bS S->bA

A->a

• Now let us draw a tree

S

​

a B

​

a B B

b S b S

b A b A

​

a

a

Back

Solution:

TOC notes by S P CHARI

Back

• We will first write all the productions that are giving terminal symbols. A->a

B->aa

But if we look at start symbol S then S->aS|A|C

There is no production for B from start symbol. Thus B become a useless symbol.

Similarly, S->C->aCb->aaCbb->….

There is no terminating symbol for C, Therefore we will eliminate C. Then the set of rules are

S->aS|A A->a

TOC notes by S P CHARI

Back

•^SC^oon^ls^uide^tr aⁱl^ol thⁿe p^:roductions that are giving terminal symbols

S->a

B->a

D->ddd

Now Consider

S->cC

C->cCD

D->ddd.

We will try to derive the string using production rule C we get ,

S->cC->ccCddd->cccCDddd->….

We will not get any terminal symbol for C. Thus we can eliminate C production . To reach D , Cis the only

production, As C is eliminated there is no point of D production. Hence , D is also eliminated.

Therefore,

S->aA|a|Bb

A->aB

B->a|Aa

Is the reduced Grammar.

Solution:

• Now the Ꜫ production is B->Ꜫ we will delete this production, And then add the production having B replaced by Ꜫ

A->0B1 if B=Ꜫ

A->01

Similarly,

A->1B1->11

A->0B1|1B1|01|11

Similarly,

B->0B->0 B->1B->1

B->0B|1B |0|1

Collectively we can write

A->0B1|1B1|01|11 B->0B|1B|0|1

Back

TOC notes by S P CHARI