Computation:

If it involves a computer, a program running on a computer and numbers going in and out
then computation is likely happening.

Theory of computation:

‐ It is a Study of power and limits of computing. It has three interacting components:

- Automata Theory
- Computability Theory
-Complexity Theory

Computability Theory: -
‐ What can be computed?
-Are there problems that no program can solve?

Complexity Theory: -

‐ What can be computed efficiently?

‐ Are there problems that no program can solve in a limited amount of time or space?

Automata Theory: -

‐ Study of abstract machine and their properties, providing a mathematical notion of ―computer‖
‐ Automata are abstract mathematical models of machines that perform computations on an
input by moving through a series of states or configurations. If the computation of an
automaton reaches an accepting configuration it accepts that input.

Study of Automata
‐ For software designing and checking behavior of digital circuits.
 ‐ For designing software for checking large body of text as a collection of web pages, to
find occurrence of words, phrases, patters (i.e. pattern recognition, string matching, …)
‐ Designing ―lexical analyzer‖ of a compiler, that breaks input text into logical units called ―tokens

Abstract Model

An abstract model is a model of computer system (considered either as hardware or software)

constructed to allow a detailed and precise analysis of how the computer system works. Such a
model usually consists of input, output and operations that can be performed and so can be
thought of as a processor. E.g. an abstract machine that models a banking system can have
operations like ―deposit‖,
―withdraw‖, ―transfer‖, etc.

Brief History:

Before 1930‘s, no any computer were there and Alen Turing introduced an abstract machine
that had all the capabilities of today‘s computers. This conclusion applies to today‘s real
machines.

Later in 1940‘s and 1950‘s, simple kinds of machines called finite automata were introduced by
a number of researchers.

In late 1950‘s the linguist N. Chomsky begun the study of formal grammar which are closely
related to abstract automata.

In 1969 S. Cook extended Turing‘s study of what could and what couldn‘t be computed and
classified the problem as:
-Decidable
-Tractable/intractable
 The basic concepts of Languages

The basic terms that pervade the theory of automata include

―alphabets,

―strings,

―languages‖, etc.

Alphabets: - (Represented by „Σ‟)

Alphabet is a finite non-empty set of symbols. The symbols can be the letters such as {a, b, c},
bits {0, 1}, digits {0, 1, 2, 3… 9}. Common characters like $, #, etc.

{0,1} – Binary alphabets

{+, −, *} – Special symbols

Strings: - (Strings are denoted by lower case letters)

String is a finite sequence of symbols taken from some alphabet. E.g. 0110 is a string
from binary alphabet, ―automata‖ is a string over alphabet {a, b, c … z}.

Empty String: -
It is a string with zero occurrences of symbols. It is denoted by ‗ε‘ (epsilon).

Length of String

The length of a string w, denoted by | w |, is the number of positions for symbols in w.

we have for every string s, length (s) ≥ 0.
| ε | = 0 as empty string have no symbols.
| 0110 | = 4

Power of alphabet

The set of all strings of certain length k from an alphabet is the kth power of that alphabet.

i.e. Σk = {w / |w| = k} If Σ = {0, 1} then,

Σ0 = {ε}

Σ1 = {0, 1}

Σ2 = {00, 01, 10, 11}

Σ3 = {000, 001, 010, 011, 100, 101, 110, 111}

Kleen Closure

The set of all the strings over an alphabet Σ is called kleen closure of Σ & is denoted by
Σ*. Thus, kleen closure is set of all the strings over alphabet Σ with length 0 or more.

∴ Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪ Σ3 ∪ ……………
E.g. A = {0}
A* = {0n/ n = 0, 1, 2, …}.

Positive Closure: -
The set of all the strings over an alphabet Σ, except the empty string is called positive closure
and is denoted by Σ+.

∴ Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪……………
Language:

A language L over an alphabet Σ is subset of all the strings that can be formed out of Σ; i.e. a
language is subset of kleen closure over an alphabet Σ; L ⊆ Σ*. (Set of strings chosen from Σ*
defines language). For example;

◻ Set of all strings over Σ = {0, 1} with equal number of 0‘s & 1‘s.
L = {ε, 01, 0011, 000111, ………}
◻ φ is an empty language & is a language over any alphabet.

◻ {ε} is a language consisting of only empty string.

◻ Set of binary numbers whose value is a
prime: L = {10, 11, 101, 111, 1011, ……}

Concatenation of Strings

Let x & y be strings then xy denotes concatenation of x & y, i.e. the string formed
by making a copy of x & following it by a copy of y.

More precisely, if x is the string of i symbols as x = a1a2a3…ai & y is the string of j symbols as y =
b1b2b3…bj then xy is the string of i + j symbols as xy = a1a2a3…aib1b2b3…bj.

For example;
x = 000
y = 111
xy = 000111 &
yx = 111000

Note: ‗ε‘ is identity for concatenation; i.e. for any w, εw = wε = w.

Suffix of a string
A string s is called a suffix of a string w if it is obtained by removing 0 or more leading
symbols in w. For example;
w = abcd
s = bcd is suffix of w.
here’s is proper suffix if s ≠ w.

Prefix of a string

A string s is called a prefix of a string w if it is obtained by removing 0 or more trailing

symbols of w. For example;
w = abcd
s = abc is prefix of w,
Here, s is proper suffix i.e. s is proper suffix if s ≠ w.

Substring

A string s is called substring of a string w if it is obtained by removing 0 or more leading

or trailing symbols in w. It is proper substring of w if s ≠ w.
If s is a string then Substr (s, i, j) is substring of s beginning at ith position & ending at jth
position both inclusive.

Problem

A problem is the question of deciding whether a given string is a member of some

particular language.
In other words, if Σ is an alphabet & L is a language over Σ, then problem is;
‐ Given a string w in Σ*, decide whether or not w is in L.
Exercises:

1. Let A be a set with n distinct elements. How many different binary relations on A
are there?

2. If ∑= {a,b,c} then find the followings

a. ∑1, ∑ 2, ∑3.

3. If ∑={0,1}. Then find the following languages

a. The language of string of length zero.
b. The language of strings of 0‘s and 1‘s with equal number of each.
c. The language {0n1n | n≥1}
d. The language {0i0j | 0≤i≤j}.
e. The language of strings with odd number of 0‘s and even number of 1‘s.

4. Define the Kleen closure and power of alphabets.

 Finite Automata (DFA and NFA)
Intuitive example

Consider a man watching a TV in his room. The TV is in ‖on‖ state. When it is switched off, the
TV goes to ―off‖ state. When it is switched on, it again goes to ―on‖ state. This can be
represented by following picture.

Switched off
TV “on” TV “off”

Switched on

The above figure is called state diagram.

A language is a subset of the set of strings over an alphabet. A language can be generated by
grammar. A language can also be recognized by a machine. Such machine is called recognition
device. The simplest machine is the finite state automaton.

Finite Automata
A finite automaton is a mathematical (model) abstract machine that has a set of ―states‖ and its
―control‖ moves from state to state in response to external ―inputs‖. The control may be either
―deterministic‖ meaning that the automation can‘t be in more than one state at any one time,
or ―non deterministic‖, meaning that it may be in several states at once. This distinguishes the
class of automata as DFA or NFA.

‐ The DFA, i.e. Deterministic Finite Automata can‘t be in more than one state at any time.
‐ The NFA, i.e. Non-Deterministic Finite Automata can be in more than one state at a time.

Applications:
The finite state machines are used in applications in computer science and data networking. For example,
finite-state machines are basis for programs for spell checking, indexing, grammar checking, searching large
bodies of text, recognizing speech, transforming text using markup languages such as XML & HTML, and
network protocols that specify how computers communicate.

Deterministic Finite Automata

Definition
A deterministic finite automaton is defined by a quintuple (5-tuple) as (Q, Σ, δ, q0, F).

Where,
Q = Finite set of states,
Σ = Finite set of input symbols,
δ = A transition function that maps Q × Σ -> Q
q0 = A start state; q0 ∈ Q
F = Set of final states; F ⊆ Q.

A transistion function δ that takes as arguments a state and an input symbol and returns a
state. In our diagram, δ is represented by arcs between states and the labels on the arcs.

For example
 If s is a state and a is an input symbol then δ(p,a) is that state q such that there are arcs
labled ‗a‘ from p to q.

General Notations of DFA

There are two preferred notations for describing this class of automata;
‐ Transition Table
‐ Transition Diagram

a) Transition Table: -

Transition table is a conventional, tabular representation of the transition function δ that takes
the arguments from Q × Σ & returns a value which is one of the states of the automation. The
row of the table corresponds to the states while column corresponds to the input symbol. The
starting state in the table is represented by -> followed by the state i.e. ->q, for q being start
state, whereas final state as
*q, for q being final state.
The entry for a row corresponding to state q and the column corresponding to input a, is the
state δ (q, a).

For example:

I. Consider a DFA;
Q = {q0, q1, q2, q3}

Σ = {0, 1}
q0 = q0
F = {q0}
 δ = Q × Σ -> Q

Then the transition table for above DFA is as follows:

δ 0 1
* -> q0 q2 q1
q1 q3 q0
q2 q0 q3
q3 q1 q2

This DFA accepts strings having both an even number of 0‘s & even number of 1‘s.

b) Transition Diagram:

A transition diagram of a DFA is a graphical representation where; (or is a graph)

‐ For each state in Q, there is a node represented by circle,

‐ For each state q in Q and each input a in Σ, if δ (q, a) = p then there is an arc from node q to p
labeled a in the transition diagram. If more than one input symbol cause the transition from
state q to p then arc from q to p is labeled by a list of those symbols.

‐ The start state is labeled by an arrow written with ―start‖ on the node.

‐ The final or accepting state is marked by double circle.

‐ For the example I considered previously, the corresponding transition diagram is:
 How a DFA process strings?

The first thing we need to understand about a DFA is how DFA decides whether or not to
―accept‖ a sequence of input symbols. The ―language‖ of the DFA is the set of all symbols that
the DFA accepts. Suppose a1, a2, …… an is a sequence of input symbols. We start out with the
DFA in its start state, q0. We consult the transition function δ also for this purpose. Say δ (q0,
a1) = q1 to find the state that the DFA enters after processing the first input symbol a1. We
then process the next input symbol a2, by evaluating δ (q1, a2); suppose this state be q2. We
continue in this manner, finding states q3, q4,
…, qn. such that δ (qi-1, ai) = qi for each i. if qn is a member of F, then input a1, a2, --- an is
accepted & if not then it is rejected.

Extended Transition Function of DFA ( ̂ ): -

The extended transition function of DFA, denoted by 𝛿̂ is a transition function that takes two
arguments as input, one is the state q of Q and another is a string w∈ Σ*, and generates a state
p ∈ Q. This state p is that the automaton reaches when starting in state q & processing the
sequence of inputs w.
i.e. 𝛿̂ (q, w) = p

Let us define by induction on length of input string as follows:

Basis step: 𝛿̂ (q,є) =q. i.e. from state q, reading no input symbol stays at the same state.

Induction: Let w be a string from Σ * such that w = xa, where x is substring of w without last
symbol and a is the last symbol of w, then 𝛿̂ (q, w) = δ (𝛿̂ (q, x), a).

Thus, to compute 𝛿̂ (q, w), we first compute 𝛿̂ (q, x), the state the automaton is in after
processing all but last symbol of w. let this state is p, i.e. 𝛿̂ (q, x) = p.

Then, 𝛿̂ (q, w) is what we get by making a transition from state p on input a, the last symbol of w.

i.e. 𝛿̂ (q, w) = δ (p, a)

For Example
Now compute 𝛿̂ (q0,1001)

c) Compute 𝛿̂ (q0,101) yourself.( ans : Not accepted by above DFA)

String accepted by a DFA

A string x is accepted by a DFA (Q, Σ, δ, q0, F) if; 𝛿̂ (q, x) = p ∈ F.

Language of DFA

The language of DFA M = (Q, Σ, δ, q0, F) denoted by L(M) is a set of strings over Σ* that
are accepted by M.
i. e; L(M) = {w/ 𝛿̂ (q0, w) = p ∈ F}

That is; the language of a DFA is the set of all strings w that take DFA starting from start state to
one of the accepting states. The language of DFA is called regular language.

Examples (DFA Design for recognition of a given language)

1. Construct a DFA, that accepts all the strings over Σ = {a, b} that do not end with ba.

2. DFA accepting all string over Σ = {0, 1} ending with 3 consecutive 0‟s.
3. DFA accepting zero or more consecutive 1‟s.
i.e. L (M) = {1n / n = 0, 1, 2, ……}
4. DFA over {0, 1} accepting {1, 01}

Non-Deterministic Finite Automata (NFA)

A non-deterministic finite automaton is a mathematical model that consists of:

‐ A set of states Q, (finite)

‐ A finite set of input symbols Σ, (alphabets)
‐ A transition function that maps state symbol pair to sets of states.
‐ A state q0 ∈ Q that is distinguished as a start (initial) state.
‐ A set of final states F distinguished as accepting (final) state. F ⊆ Q.

Thus, NFA can also be interpreted by a quintuple; (Q, Σ, δ, q0, F) where δ is Q × Σ =2Q. Unlike
DFA, a transition function in NFA takes the NFA from one state to several states just with a
single input.
Example:

Here, from state q1, there is no any arc for input symbol 0 & no any arc out of q2 for 0 & 1. So,
we can conclude in a NFA, there may be zero no. of arcs out of each state for each input
symbol. While in DFA, it has exactly one arc out of each state for each input symbol.

δ, the transition function is a function that takes a state in Q and an input symbol in ∑ as
arguments and returns a subset of Q The only difference between an NFA and DFA is in type of
value that δ returns. In NFA, δ returns a set of states and in case of DFA it returns a single state.

For input sequence w = 00101, the NFA can be in the states during the processing of the input are as:
2. NFA over {0, 1} accepting strings {0, 01, 11}.
The Extended transition function of NFA
As for DFA‘s, we need to define the extended transition function 𝛿̂ that takes a state q and a
string of input symbol w and returns the set of states that is in if it starts in state q and
processes the string w.

Definition by Induction:

Basis Step: 𝛿̂ (q, ε) = {q} i.e. reading no input symbol remains into the same state.

Induction: Let w be a string from Σ* such that w = xa, where x is a substring of without last
symbol a.

Also let,
𝛿̂ (q, x) = {p1, p2, p3, …pk}
and

Then, 𝛿̂ (q, w) = {r1, r2, r3, …rm}

Thus, to compute 𝛿̂ (q, w) we first compute 𝛿̂ (q, x) & then following any transition from
each of these states with input a.

Consider, a NFA,
Now, computing for 𝛿̂ (q0, 01101)

Since the result of above computation returns the set of state {q0,q2) which include the
accepting state q2 of NFA so the string 01101 is accepted by above NFA.

Examples (Design NFA to recognize the given language)

1. Construct a NFA over {a, b} that accepts strings having aa as substring.

2. NFA for strings over {0, 1} that contain substring 0110 or 1001
3. NFA over {a, b} that have “a” as one of the last 3 characters.
4. NFA over {a, b} that accepts strings starting with a and ending with b.

Equivalence of NFA & DFA

Although there are many languages for which NFA is easier to construct than DFA, it can be
proved that every language that can be described by some NFA can also be described by some
DFA.

The DFA has more transition than NFA and in worst case the smallest DFA can have 2 n state
while the smallest NFA for the same language has only n states.

We now show that DFAs & NFAs accept exactly the same set of languages. That is non-
determinism does not make a finite automaton more powerful.

To show that NFAs and DFAs accept the same class of language, we show;

Any language accepted by a NFA can also be accepted by some DFA. For this we describe an
algorithm that takes any NFA and converts it into a DFA that accepts the same language. The
algorithm is called ―subset construction algorithm‖.

The key idea behind the algorithm is that; the equivalent DFA simulates the NFA by keeping
track of the possible states it could be in. Each state of DFA corresponds to a subset of the set
 of states of the NFA, hence the name of the algorithm. If NFA has n-states, the DFA can have 2 n
states (at most), although it usually has many less.

The steps are:

To convert a NFA, N = (QN, Σ, δN, q0, FN) into an equivalent DFA D = (QD, Σ, δD, q0, FD), we have
following steps.

1. The start state of D is the set of start states of N i.e. if q0 is start state of N then D has start
state as {q0}.

2. QD is set of subsets of Q N i.e. QD = 2QN. So, QD is power set of QN. So if QN has n states then QD
will have 2n states. However, all of these states may not be accessible from start state of Q D so
they can be eliminated. So QD will have less than 2n states.

3. FD is set of subsets S of QN such that S ∩ FN ≠ φ i.e. FD is all sets of N‘sstates that include at
least one final state of N.

each set S ⊆ QN & each input a ∈ Σ, δD (S, a)=

For

i.e. for any state {q0, q1, q2, … qk} of the DFA & any input a, the next state of the DFA is the set
of all states of the NFA that can result as next states if the NFA is in any of the state‘s q0, q1, q2,
… qk when it reads a.
Example 1
The same table can be represented with renaming the state on table entry as

The equivalent DFA is

Or

The other state is removed because they are not reachable from start state.
Example 2:

Solution: using the subset construction we have the DFA as

Draw the DFA diagram from above transition table yourself.

Exercises

1. Convert the following NFA to DFA

2. Convert NFA to DFA

 Minimization of DFA
The DFA minimization is the process of reducing states in a deterministic finite automaton (DFA) and
maintaining its language recognition abilities. That means, DFA minimization is aimed at finding a DFA with the
least number of states that can recognize the same language as the original DFA.
Some of the benefits of minimizing DFA:
Reduced memory usage: DFAs with fewer states require less memory to store. This can be important for
applications where memory usage is a constraint.
Improved computational efficiency: DFAs with fewer states can process strings more quickly. This can be
important for applications where processing speed is a concern.
Enhanced understanding: DFAs with fewer states are generally easier to understand and analyze. This can be
helpful for debugging and maintaining DFAs.
Simplified hardware implementation: DFAs with fewer states are more amenable to hardware
implementation. This can be important for applications where performance is critical.

Example of DFA minimization: Construct a minimum state automata equivalent to given automata?

Solution:
Transition table for above automata.
State Input = a Input = b

->q0 Initial state q1 q3

q1 q2 q4

q2 q1 q1

q3 q2 q4

q4 Final state q4 q4

Step 01: Remove steps which are unreachable from initial states.

Step 02: Split final states and non-final states.

 A0 = {q4}
 A1 = {q0,q1,q2,q3}
 π0 = {q4}, {q0,q1,q2,q3}
 A0 cannot be partition further.
In A1,

 q0 is 1 equivalent to q2 for input a, but not equivalent to q1 and q3.

 q1 is 1 equivalent to q3 for input a and b, but not to q0 and q2.
So, A1 can be partitioned as,

 B0 = {q0, q2}
 B1 = {q1, q3}
 π1 = {q4}, {q0,q2}, {q1,q3}
Now, B0 and B1 cannot be partitioned further.

 π2 = {q4}, {q0,q2}, {q1,q3}

 π2 = π1
In minimized DFA, we have three states,

 {q4},
 {q0,q2},
 {q1,q3}

Minimized DFA:

State Input = a Input = b

->{q0,q2} Initial state {q1,q3} {q1,q3}

{q1,q3} {q0,q2} {q4}

{q4} Final state {q4} {q4}

Chapter 2

Chapter 2: Regular Expressions and Regular Languages (4 Hours)

1. Regular Expressions

A Regular Expression (RegEx) is a sequence of characters that defines a search pattern, mainly used for
pattern matching in strings. It is a formal way to represent regular languages using symbols and operators.

Operators in Regular Expressions

 Concatenation: ab → Matches "ab".

 Union (| or +): a|b → Matches "a" or "b".
 Kleene Star (*): a* → Matches zero or more occurrences of "a".
 Kleene Plus (+): a+ → Matches one or more occurrences of "a".
 Optional (?): a? → Matches "a" or an empty string.
 Brackets []: [a-z] → Matches any lowercase letter from a to z.

Examples of Regular Expressions

1. Email Validation:

css
CopyEdit
^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$

o Matches email addresses like user@example.com.

2. Phone Number Pattern (US Format):

ruby
CopyEdit
^\(\d{3}\) \d{3}-\d{4}$

o Matches phone numbers like (123) 456-7890.

3. Binary String with Even Number of 0s:

markdown
CopyEdit
(1*01*01*)*

o Matches strings like "00", "1100", "1010".

2. Connection Between Regular Expressions and Regular Languages

A regular language is any language that can be expressed using a regular expression and can be recognized by
a finite automaton (DFA/NFA).

Examples of Regular Expressions & Corresponding Regular Languages

1. Language of all binary strings ending in "01"

o Regular Expression: (0|1)*01
o Example Strings: "01", "101", "1101".

2. Language of strings containing at least one "a"

o Regular Expression: .*a.*
o Example Strings: "abc", "aaa", "ba".

3. Language of strings with only even-length sequences of 0s

o Regular Expression: (1*00)*
o Example Strings: "00", "1100", "0000".

3. Regular Grammar

A Regular Grammar is a set of rules (productions) that define a regular language. These grammars can be:

 Right Linear Grammar: Productions have the form A → aB or A → a.

 Left Linear Grammar: Productions have the form A → Ba or A → a.

Examples of Regular Grammar

1. Binary Strings Ending in "1"

o Grammar:

nginx
CopyEdit
S → 0S | 1S | 1

o Example Strings: "1", "01", "101", "1101".

2. Strings with an Even Number of 0s

o Grammar:

less
CopyEdit
S → 1S | 0A
A → 1A | 0S | ε

o Example Strings: "00", "1100", "0000".

3. Strings Over {a, b} that Start with 'a'

 o Grammar:

less
CopyEdit
S → aA
A → aA | bA | ε

o Example Strings: "a", "ab", "aab", "abb".

4. Pumping Lemma and Non-Regular Languages

The Pumping Lemma is a property used to prove that a language is not regular. It states that for any regular
language, there exists a constant p such that any string w with length ≥ p can be divided into three parts xyz,
where:

1. |xy| ≤ p
2. |y| > 0
3. xyⁿz is in L for all n ≥ 0

Examples of Non-Regular Languages

1. L = {aⁿbⁿ | n ≥ 0}
o Strings like "ab", "aabb", "aaabbb" are in L.
o Cannot be recognized by a finite automaton since it requires counting.

2. L = {ww^R | w ∈ {0,1}*} (Palindrome Language)

o Strings like "0110", "10101" are in L.
o Requires a stack (hence not regular).

3. L = {aⁿbⁿcⁿ | n ≥ 0}
o Strings like "abc", "aabbcc" are in L.
o Requires three-way matching, which finite automata cannot do.

Summary

 Regular Expressions define Regular Languages using symbols and operators.

 Regular Grammars generate Regular Languages and can be Right/Left Linear.
 Pumping Lemma helps prove Non-Regular Languages that cannot be recognized by finite automata.

Would you like more detailed explanations or alternative examples? 😊

4o
You said:
more detail for each

ChatGPT said:

Chapter 2: Regular Expressions and Regular Languages (4 Hours)

In this chapter, we will cover regular expressions, their connection to regular languages, regular
grammars, and the Pumping Lemma, which helps identify non-regular languages. Each concept will be
explained in detail with three examples.

1. Regular Expressions

A Regular Expression (RegEx) is a formal notation used to define patterns in strings. Regular expressions
describe a set of strings that belong to a regular language, which can be recognized by finite automata.

Regular Expression Operators and Meaning

Operator Symbol Meaning Example
Concatenation ab Matches "ab" exactly abc matches "abc"
Union (OR) `a b` Matches "a" or "b"
Kleene Star a* Matches zero or more occurrences of "a" a* matches "", "a", "aa", "aaa"
Kleene Plus a+ Matches one or more occurrences of "a" a+ matches "a", "aa", "aaa" but not ""
Optional a? Matches zero or one occurrence of "a" a?b matches "b" or "ab"
Bracket Notation [a-z] Matches any character from "a" to "z" [0-9] matches "0" to "9"

Examples of Regular Expressions

1. Email Validation

css
CopyEdit
^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$

o This matches a valid email format such as user@example.com or test.email@domain.co.in.

2. Matching Phone Numbers (US Format)

ruby
CopyEdit
^\(\d{3}\) \d{3}-\d{4}$

o This matches numbers like (123) 456-7890.

3. Binary Strings with an Even Number of 0s

 markdown
CopyEdit
(1*01*01*)*

o This ensures that each "0" appears in pairs, making it valid for strings like "00", "1100", and "1010".

2. Connection Between Regular Expressions and Regular Languages

A Regular Language is a language that can be described using a regular expression and can be recognized by
a finite state machine (DFA or NFA).

Examples of Regular Expressions & Corresponding Regular Languages

1. Language of all binary strings ending in "01"

o Regular Expression: (0|1)*01
o Example Strings: "01", "101", "1101".
o Finite Automaton: A DFA can be designed to track whether the last two characters of input are "01".

2. Language of strings containing at least one "a"

o Regular Expression: .*a.*
o Example Strings: "a", "abc", "ba".
o Finite Automaton: A DFA can transition to an accepting state as soon as it encounters "a".

3. Language of strings with only even-length sequences of 0s

o Regular Expression: (1*00)*
o Example Strings: "00", "1100", "0000".
o Finite Automaton: A DFA can count pairs of "0" and accept only if pairs are complete.

3. Regular Grammar

A Regular Grammar is a formal grammar that generates a regular language. It consists of production rules
that replace non-terminal symbols with terminal symbols in a specific manner.

Types of Regular Grammar

 Right Linear Grammar: Productions are of the form A → aB or A → a.

 Left Linear Grammar: Productions are of the form A → Ba or A → a.

Examples of Regular Grammar

1. Binary Strings Ending in "1"

o Grammar Rules:
 nginx
CopyEdit
S → 0S | 1S | 1

o Example Strings: "1", "01", "101", "1101".

o Explanation: The string can start with any number of "0"s or "1"s but must end with "1".

2. Strings with an Even Number of 0s

o Grammar Rules:

less
CopyEdit
S → 1S | 0A
A → 1A | 0S | ε

o Example Strings: "00", "1100", "0000".

o Explanation: "0"s appear in pairs and "1"s do not affect the pattern.

3. Strings Over {a, b} that Start with 'a'

o Grammar Rules:

less
CopyEdit
S → aA
A → aA | bA | ε

o Example Strings: "a", "ab", "aab", "abb".

o Explanation: The first character must be "a", followed by any sequence of "a" and "b".

4. Pumping Lemma and Non-Regular Languages

The Pumping Lemma is a property used to prove that a language is not regular.

Pumping Lemma Conditions

For any regular language L, there exists a constant p (pumping length) such that any string w in L with |w| ≥
p can be divided into three parts xyz, where:

1. |xy| ≤ p
2. |y| > 0
3. xyⁿz is in L for all n ≥ 0

If a language fails to satisfy the Pumping Lemma, it is not regular.

Examples of Non-Regular Languages

1. L = {aⁿbⁿ | n ≥ 0}
o Example Strings: "ab", "aabb", "aaabbb".
o Why Not Regular?: The finite automaton cannot remember how many "a"s were read before reading
"b"s.

2. L = {ww^R | w ∈ {0,1}*} (Palindrome Language)

o Example Strings: "0110", "10101".
o Why Not Regular?: Recognizing palindromes requires storing half of the input, which a finite automaton
cannot do.

3. L = {aⁿbⁿcⁿ | n ≥ 0}
o Example Strings: "abc", "aabbcc".
o Why Not Regular?: The finite automaton cannot keep track of three different counts simultaneously.

Summary
Concept Explanation
Regular Expressions Define patterns that match regular languages.
Regular Languages Can be expressed using regular expressions and recognized by finite automata.
Regular Grammar Generates regular languages using right or left linear rules.
Pumping Lemma Helps prove that certain languages are not regular.

Would you like a detailed DFA or NFA construction for any of these examples? 😊

4o

You said:
regular language and non regular language different

ChatGPT said:

Difference Between Regular and Non-Regular Languages

Regular and non-regular languages are classifications of formal languages based on whether they can be
recognized by a finite automaton.

Feature Regular Language Non-Regular Language

A language that can be described using a A language that cannot be recognized by a finite
Definition regular expression and recognized by a finite automaton and requires a more powerful computational
automaton (DFA/NFA). model (e.g., a pushdown automaton).
Requires a pushdown automaton (for context-free
Recognized by a finite state machine
Recognition languages) or a Turing machine (for more complex
(DFA/NFA) with a finite number of states.
languages).
 Feature Regular Language Non-Regular Language
Memory No memory (stack or tape) – it only depends Needs memory (stack or tape) to track relationships
Requirement on the current state. between input symbols.
Operations Closed under union, intersection,
May not be closed under these operations.
Supported complement, and concatenation.
Regular Expressions or Finite Automata Context-Free Grammars (CFG) or more complex
Described By
(DFA/NFA). grammars.
Using Pumping Lemma to show that no finite
Proved By Constructing a DFA/NFA for the language.
automaton can recognize the language.

Examples of Regular and Non-Regular Languages

Examples of Regular Languages

These languages can be recognized using a finite automaton (DFA/NFA).

1. Set of Binary Strings Ending in "01"

o Regular Expression: (0|1)*01
o Example Strings: "01", "101", "00001".
o Finite Automaton: Can track the last two characters and accept if they are "01".

2. Set of Strings Containing an Even Number of "0"s

o Regular Expression: (1*01*01*)*
o Example Strings: "00", "1100", "1010".
o Finite Automaton: Can toggle between two states to count even occurrences of "0".

3. Strings Over {a, b} That Start with 'a'

o Regular Expression: a(a|b)*
o Example Strings: "a", "ab", "aab".
o Finite Automaton: Starts in a state that only transitions if the first letter is "a".

Examples of Non-Regular Languages

These languages cannot be recognized by a finite automaton because they require counting or tracking long-
distance dependencies.

1. L = { aⁿbⁿ | n ≥ 0 }
o Example Strings: "ab", "aabb", "aaabbb".
o Why Not Regular?: The finite automaton cannot count the number of "a"s and match them with the
same number of "b"s.

2. L = { w w^R | w ∈ {0,1} }* (Palindrome Language)

o Example Strings: "0110", "10101".
 o Why Not Regular?: The finite automaton cannot store the first half of the string to compare it with the
second half.

3. L = { aⁿbⁿcⁿ | n ≥ 0 }
o Example Strings: "abc", "aabbcc", "aaabbbccc".
o Why Not Regular?: Requires matching three different counts, which a finite automaton cannot track.

How to Prove a Language is Non-Regular? (Using Pumping Lemma)

1. Assume the language is regular.

2. Use the pumping lemma: Any sufficiently long string in the language can be split into three parts xyz, where:
o |xy| ≤ p
o |y| > 0
o xyⁿz is in L for all n ≥ 0
3. Show that for some string in the language, no such division exists that satisfies the above conditions.
4. Conclude that the language is not regular.

Summary
Aspect Regular Language Non-Regular Language
Recognized By DFA/NFA (Finite Automaton) Pushdown Automaton / Turing Machine
Memory Needed? No memory (limited states) Needs memory (stack/tape)
Example Languages `{ w w ends in "01" }, { w
Proof Technique Construct DFA/NFA Use Pumping Lemma to show it’s not regular