UNIT 4

[Link] machine :- Turing machines are an important tool for studying the limits of
computation and for understanding the foundations of computer science .

A Turing Machine consists of a tape of infinite length on which read and writes
operation can be performed. The tape consists of infinite cells on which each cell either
contains input symbol or a special symbol called blank. It also consists of a head pointer
which points to cell currently being read and it can move in both directions

Components of a Turing Machine:

 Infinite Tape: The tape is a memory medium where the machine reads, writes, and moves a
read/write head.
 Tape Head: This head reads and writes symbols on the tape and can move left or right.

 State Transition Table:This table defines how the machine changes its state, reads/writes
symbols, and moves the head based on the current state and the symbol being read.
 Finite Control Unit:This unit, which can be thought of as the "brain" of the machine, has a
finite number of states and manages the operations based on the transition table


Turing Machine Formalism

A Turing Machine is defined by:
1. A finite set of states (Q).
2. An input alphabet (Σ).
3. A tape alphabet (Γ) that includes Σ.
4. A transition function (δ).
5. A start state (q0).
6. A blank symbol (B).
7. A set of final states (F).
Example: Turing Machine

We construct a Turing Machine (TM) for the language L = {0ⁿ1ⁿ | n ≥ 1}, which accepts
strings of equal 0s followed by equal 1s.
Components:
 Q = {q₀, q₁, q₂, q₃} (q₀ is the initial state)
 T = {0,1,X,Y,B} (B represents blank, X and Y mark processed symbols)
 Σ = {0,1} (input symbols)
 F = {q₃} (final state)
  : Q x   Q x  x {L, R}

Transition Table:

see how this turing machine works for 0011. Initially head points to 0 which is underlined and
state is q0 as:

The move will be δ(q0, 0) = (q1, X, R). It means, it will go to state q1, replace 0 by X and
head will move to right as:

The move will be δ(q1, 0) = (q1, 0, R) which means it will remain in same state and without
changing any symbol, it will move to right as:
The move will be δ(q1, 1) = (q2, Y, L) which means it will move to q2 state and changing 1 to
Y, it will move to left as:

Working on it in the same way, the machine will reach state q3 and head will point to B as
shown:

Using move δ(q3, B) = halt, it will stop and accepted.

Note:
 In non-deterministic turing machine, there can be more than one possible move for a given
state and tape symbol, but non-deterministic TM does not add any power.
 Every non-deterministic TM can be converted into deterministic TM.
 In multi-tape turing machine, there can be more than one tape and corresponding head
pointers, but it does not add any power to turing machine.
 Every multi-tape TM can be converted into single tape TM.

[Link] Turing Machine :- A Universal Turing Machine is a Turing Machine which

when supplied with an appropriate description of a Turing Machine M and an input string w,
can simulate the computation of w.

Universal Turing Machine is a 7-tuple machine represented as:

Tu = (Q, , , , qo, F)
where: Q = the set of all internal states
= the input alphabet
= finite set of symbols called the tape alphabet
= the transition function
q0Q = the initial state
B = a special symbol called blank
FQ = the set of all final states.

Construction of UTM
Without loss of generality, we assume the following for M:
 Q = {q1, q2, ....qn} where q1=initial state and q2=Final State
 τ = {σ1, σ2,,...σn} where σ represent blanks
 Select an encoding on which q1 is representable by 1, q2 by 11, and so on.
 Similarly, σ1 is encoded as 1, σ2 as 11, etc.
 Finally, let us represent R/W head directions by 1 for L (Left) and 11 for R(Right).
 The symbol 0 will be used as a separator between 1s.
With this scheme, any transition of M can be given as :

Input Alphabet:

 The UTM, named Mu, works with the binary alphabet: {0, 1}.

Tapes Used:

The multi-tape UTM uses three tapes:

1. Tape 1: Contains the encoding of machine M.

2. Tape 2: Contains the encoding of M's tape (i.e., M's input and tape contents).
3. Tape 3: Contains the encoding of M's current state and head position.
Diagram Labels:

 Finite Control of Mu: The brain of the UTM.

 Tape 1: Contains encoded transitions (rules) of M.
 Tape 2: Simulates M’s tape.
 Tape 3: Holds M’s current state and head position.

Working of UTM Mu:

1. Reads ID (Instantaneous Description):

o Mu first reads Tape 2 and Tape 3 to determine the current configuration (ID) of
machine M. This includes the tape contents, current state, and head position.
2. Consults Tape 1:
o Based on the ID, Mu then looks at Tape 1 to check what M would do next (i.e.,
what transition to perform according to M's transition function).
3. Performs Transition:
o Finally, Mu updates Tape 2 and Tape 3 to reflect the result of M's move:
 Changes symbol(s) on M’s tape.
 Updates the state.
 Moves the head left/right.

3. Linear Bounded Automaton (LBA)

A Linear Bounded Automaton is a type of Turing Machine with a restricted tape size. The
tape is bounded by a constant times the length of the input, meaning it cannot use more
space than what's proportional to the input size.

It recognizes context-sensitive languages.

A Linear Bounded Automaton (LBA) is similar to Turing Machine with some properties
stated below:
 Turing Machine with Non-deterministic logic ,
 Turing Machine with Multi-track, and
 Turing Machine with a bounded finite length of the tape.

Tuples Used in LBA :
LBA can be defined with eight tuples (elements that help to design automata) as:
M = (Q , T , E , q0 , M L , MR , S , F),

where,
Q -> A finite set of transition states
T -> Tape alphabet
E -> Input alphabet
q0 -> Initial state
ML -> Left bound of tape
MR -> Right bound of tape
S -> Transition Function
F -> A finite set of final states
Diagrammatic Representation of LBA :

Example Language
Let’s consider this context-sensitive language:

L = { aⁿbⁿcⁿ | n ≥ 1 }

This language consists of strings where:

 There are n as,

 followed by n bs,
 followed by n cs.

Valid strings:
 abc (n=1)
  aabbcc (n=2)
 aaabbbccc (n=3)

Invalid strings:
 aabcc (unequal numbers)
 abcc (order issue)
 aaabbccc (extra a or b)

How LBA Accepts This Language

Here’s the working of an LBA for string aaabbbccc:

1. Mark the first a (e.g., change it to X)

2. Move right, find the first unmarked b, mark it as Y.
3. Move further, find the first unmarked c, mark it as Z.
4. Go back to the left and repeat the process for the next unmarked a.
5. If all a’s, b’s, and c’s are marked equally and correctly — LBA accepts the input.

If the counts mismatch or symbols are out of order — LBA rejects.

4. Recognizing a Language in a Turing Machine

A Turing Machine (TM) is a powerful computational model used to recognize (or decide)
languages. Here's how it works:

1. What Does “Recognize” Mean?

A Turing Machine recognizes a language L if:

 For every string w ∈ L, the machine eventually halts and accepts.

 For every string w ∉ L, the machine either halts and rejects, or loops forever (does not
halt).

Such a language is called a recursively enumerable language.

2. Example: Recognizing a Simple Language

L = { w ∈ {a, b}* | w contains equal number of a's and b's }

Language:
Valid strings: ab, aabb, abab, baba
Invalid strings: aaa, abb, aab

How a Turing Machine Recognizes L:

1. It scans the tape to find an unmarked ‘a’, replaces it with a special symbol like X.
2. Then it scans to the right to find an unmarked ‘b’, and replaces it with Y.
3. It repeats this process until:
o All a and b are marked — ACCEPT.
o One is left without a pair — REJECT.
o Or if it cannot find a matching symbol — REJECT.

This machine recognizes the language because:

 It accepts strings in L.
 It may reject or loop on strings not in L.

5. Context-Sensitive Languages (CSL)

Context-Sensitive Languages are a class of formal languages that are more powerful than
context-free languages, but less powerful than recursively enumerable languages.

1. Definition

A Context-Sensitive Language (CSL) is a language that can be accepted by a Linear

Bounded Automaton (LBA).

Formally, a grammar G = (V, Σ, P, S) generates a context-sensitive language if all production

rules are of the form:

α→β
such that
|β| ≥ |α|,(Length of the right side is greater than or equal to the left side)
and α ≠ ε (epsilon) — i.e., no rule can reduce the length of the string.

This is called non-contracting grammar.

2. Example of Context-Sensitive Language

L = { aⁿbⁿcⁿ | n ≥ 1 }
This means: equal number of a’s, b’s, and c’s in that exact order.

 Valid: abc, aabbcc, aaabbbccc

 Invalid: aabcc, aaabbbcc

This language is context-sensitive, because:

 It has equal number of a’s, b’s, and c’s.

 It cannot be generated by a context-free grammar.
 But it can be generated by a context-sensitive grammar and accepted by an LBA.

3. Characteristics of CSL

Feature Description
Recognized Linear Bounded Automata (LBA)
by
Grammar Type 1 (Context-Sensitive Grammar)
Type

Closure Closed under union, intersection,

Properties concatenation, etc.
Decision Membership is decidable (i.e., you can
Problems check if a string belongs)

6. Recursively Enumerable Languages (RE Languages)

Recursively Enumerable Languages are the class of languages that can be recognized by a
Turing Machine (TM). They represent the most general class in the Chomsky hierarchy.
RE languages or type-0 languages are generated by type-0 grammars.
An RE language can be accepted or recognized by Turing machine which means it will enter
into final state for the strings of language and may or may not enter into rejecting state for the
strings which are not part of the language. It means TM can loop forever for the strings which
are not a part of the language. RE languages are also called as Turing recognizable languages.
1. Formal Definition

A language L is called recursively enumerable (RE) if there exists a Turing Machine M such
that:

 If w ∈ L, then M accepts w (halts and enters an accept state).

 If w ∉ L, then M may either reject w or loop forever.

Example of a Recursively Enumerable (RE) Language:

🧠 Language Definition:

L = { w ∈ {a, b}* | w contains equal number of a’s and b’s }

This means the language contains all strings where the number of a's is equal to the number of
b's, in any order.

✅ Examples of strings in L:
 ab
 aabb
 baba
 abab
 bbaa

❌ Not in L:
 aaa
 bbba
 aab

🧮 Why This Is Recursively Enumerable:

A Turing Machine can be built to:
 Scan the tape to find an unmarked a, mark it.
 Then search for an unmarked b, mark it.
 Repeat this process.
 If all a's and b's are paired, accept the string.
 If leftover a's or b's remain, or if no match is found, reject or loop.

This TM may not halt if it can't match the string properly — but that's allowed in RE languages.
So this language is not necessarily recursive (decidable), but it is recursively enumerable.
Would you like the Turing Machine diagram or transition table for this example?

7. Recursive language
A recursive language is a language for which there exists a Turing Machine that always halts
(accepts or rejects) for every input string. This means the language is decidable.
✅ Example of a Recursive Language:

Let’s define the language:

L = { w ∈ {a, b}∗ | w has equal number of a’s and b’s and all a’s appear before b’s }

This means:

 The string consists of a’s followed by an equal number of b’s.

 It follows the pattern: anbn, where n ≥ 0.

✔ Strings in L:

 ε (empty string)
 ab
 aabb
 aaabbb

✘ Not in L:

 abb (more b’s than a’s)

 aab (not equal count)
 baba (b appears before a)

🧠 Why It Is Recursive:

We can construct a Turing Machine that:

1. Scans the input string left to right.

2. Replaces one a with X, then finds and replaces one b with Y.
3. Repeats this until all a’s and b’s are marked.
4. If at any step the number of a’s and b’s don’t match, the machine halts and rejects.
5. If all are matched, the machine halts and accepts.

💡 This machine always halts — either it accepts or rejects the input — so the language is
recursive.

Difference Between Recursive and RE Languages

Property Recursive Language Recursively Enumerable
Language
Accepted by Turing Machine that always Turing Machine (may not halt)
halts
Halts for all Yes Not necessarily
inputs?
Decidability Decidable Semi-decidable

8. Unrestricted Grammar (Type-0 Grammar)

An unrestricted grammar is the most general type of grammar in the Chomsky hierarchy. It is
also called a Type-0 grammar, and it generates recursively enumerable languages.

1. Formal Definition
An unrestricted grammar is a grammar G = (V, Σ, P, S) where:

 V = set of variables (non-terminals)

 Σ = set of terminal symbols
 P = set of productions (rules)
 S = start symbol

Each production in P has the form:

α→β

where:

α ∈ (V ∪ Σ)+ (i.e., α must be a non-empty string of variables and terminals),

β ∈ (V ∪ Σ)* (β can be any string of terminals and variables),


 No restrictions on the length of α or β.

2. Characteristics
Property Description

Grammar Type Type-0 (Unrestricted)

Language Generated Recursively Enumerable (RE) Languages

Recognized by Turing Machine

Production Rule Form α → β where α ≠ ε

Most General Yes — can describe any computable language

3. Example of Unrestricted Grammar
Let’s define a grammar for:
L = { aⁿbⁿcⁿ | n ≥ 1 } — not context-free, but context-sensitive and can also be generated by
unrestricted grammar.

Production rules (rough idea):

1. S → aSBC | abc
2. CB → HB
3. HB → HC
4. HC → BC
5. aB → ab
6. bB → bb
7. bC → bc
8. cC → cc

(This example simulates matching counts of a, b, and c through intermediate symbols.)

Why Is It Called “Unrestricted”?

Because:

 There are no constraints on how the left-hand side and right-hand side of productions
relate.
 Unlike CFG or CSG, it allows any transformation as long as the left side is non-empty.