1.
Discuss about Turing Machine
A Turing Machine (TM) is a theoretical computational model introduced by Alan Turing. It
is used to define and study the limits of computation. A TM consists of an infinite tape
divided into cells, a finite control unit, and a read/write head. It operates by reading a
symbol from the tape, writing a new symbol, moving the head left or right, and
transitioning between states based on a predefined set of rules. Turing Machines can
simulate any algorithm, making them fundamental to computer science.
2. Formal Definition of Turing Machine
TM = (Q, Σ, Γ, δ, q0, B, F)
Where: 1. Q: States
2. Σ: Input alphabet
3. Γ: Tape alphabet
4. δ: Transition function
5. q0: Initial state
6. B: Blank symbol
7. F: Final states
3. LBA (Linear Bounded Automaton)
A Linear Bounded Automaton (LBA) is a type of Turing machine that has a limited
amount of tape. The tape is bounded by a linear function of the input size.
*Formal Definition of LBA*.
LBA = (Q, Σ, Γ, δ, q0, F, B)
Where: 1. Q is a finite set of states
2. Σ is a finite input alphabet
3. Γ is a finite tape alphabet
4. δ is a transition function: Q × Γ → Q × Γ × {L, R}
5. q0 is the initial state
6. F is a set of final states
7. B is the bound on the tape length
4. Multi-Tape Turing Machine
A Multi-Tape Turing Machine is an extension of a standard Turing Machine with multiple
tapes, each having its own read/write head. This model enhances efficiency by allowing
simultaneous access to multiple data streams.
Formal Definition. A multi-tape Turing Machine is defined as , where:
•M = (Q, Σ, Γ, δ, q0, F) is the formal definition of a Multi-Tape Turing Machine.
where Qxk -> Q x kx {L,R ,S} k is the number of tapes.
Each tape head operates independently, reading, writing, and moving left, right, or
staying still. Although faster, multi-tape TMs have equivalent computational power to
single-tape TMs.
5. Deterministic vs. Non-Deterministic Turing Machine
Feature Deterministic TM. Non-Deterministic TM
Transition Function Single next move for each state-symbol pair. Multiple possible
moves.
Execution Path One computation path. Multiple computation paths.
Acceptance Accepts if a single path reaches . Accepts if any path reaches .
6. Recursive vs. Recursively Enumerable Languages
Feature Recursive Language Recursively Enumerable Language
Definition Decidable by a TM that always halts. Semi-decidable, TM may not
halt.
Halting Behavior Halts for all inputs. May loop for invalid inputs.
Example Palindromes. . Halting problem.
7. Discuss Chomsky Normal Form (CNF)
Chomsky Normal Form (CNF) is a simplified representation of Context-Free Grammars
(CFGs) where every production rule satisfies specific constraints. A grammar is in CNF if
all production rules are of the form:
1. A-> BC where A.B.C are non-terminal symbols, and B,C=S(start symbol).
2. A-> awhere a is a terminal symbol.
3. S->€ is allowed only if € is in the language.
Properties: CNF is useful for parsing algorithms like the CYK algorithm, which
determines membership in polynomial time. Any CFG can be converted to CNF.
8 Discuss PDA with Example
A Pushdown Automaton (PDA) is a computational model used to recognize Context-
Free Languages (CFLs). It extends finite automata by using a stack as auxiliary memory
to store information.
Example: PDA for the language :
• Push each  onto the stack.
• For each , pop an  from the stack.
• Accept if the stack is empty after processing the input.
9 Formal Definition of PDA
A Pushdown Automaton (PDA) is a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F), where:
PDA = (Q, Σ, Γ, δ, q0, Z0, F)
Where:
1. Q: States
2. Σ: Input alphabet
3. Γ: Stack alphabet
4. δ: Transition function
5. q0: Initial state
6. Z0: Initial stack symbol
7. F: Final states
Context-Free Languages are closed under:
1. Union: If L1and L2 are CFLs, L1U L2 is also a CFL.
2. Concatenation: L1L2is a CFL.
3. Kleene Star: L1*is a CFL.
4. Reversal: Reversing strings in a CFL yields another CFL.
Not Closed Under:
1. Intersection.
2. Complement.
11. Pumping Lemma for CFL
The Pumping Lemma helps prove that a language is not context-free. For a CFL L there
exists a constant p (pumping length) such that any string s€L with can be divided as
|s|>p where:
1. |vwx| < 9
2. |vx|> 1
3. uvi wxi y€L for i>0
If no such division exists, Lis not context-free.
12. Discuss Context-Sensitive Grammar (CSG)
A Context-Sensitive Grammar generates Context-Sensitive Languages (CSL). The
production rules are of the form:
1. A where A is a non-terminal, € (N U T)* , and || > |A|.
CSGs are more expressive than CFGs and can represent problems solvable in linear
space, such as the language L= {anbncn} | n>1}
13..Discuss Unrestricted Grammar
An Unrestricted Grammar has no restrictions on its production rules, allowing any form
-> where  and are strings of terminals and non-terminals, and =€
Unrestricted grammars generate Recursively Enumerable Languages (RELs), which are
the most expressive class of languages. They correspond to the computational power of
a Turing Machine.
Here are the explanations:
14.Pumping Lemma for Regular Language*
The Pumping Lemma states that for any regular language L, there exists a pumping
length p such that any string w in L with length ≥ p can be divided into three substrings w
= xyz, where:
- |y| ≥ 1
- |xy| ≤ p
- For all i ≥ 0, xy^i z ∈ L
This lemma helps prove that a language is not regular.
15. Closure Properties of Regular Set*
Regular sets are closed under:
- Union: L1 ∪ L2 is regular if L1 and L2 are regular.
- Concatenation: L1 L2 is regular if L1 and L2 are regular.
- Kleene Star: L* is regular if L is regular.
Example: If L1 = {a} and L2 = {b}, then L1 ∪ L2 = {a, b} is regular.
16...Context-Free Grammar (CFG)*
A CFG is a 4-tuple (V, Σ, P, S), where:
- V is a set of non-terminal symbols.
- Σ is a set of terminal symbols.
- P is a set of production rules.
- S is the start symbol.
17. Comparison of CFG and Regular Grammar*
| | Context-Free Grammar (CFG) | Regular Grammar (RG) |
| --- | --- | --- |
| *Expressive Power* | More expressive | Less expressive |
| *Production Rules* | Can have arbitrary production rules | Limited to regular
production rules |
| *Parsing* | More complex parsing | Simpler parsing |
18. Ambiguity in Grammar*
A grammar is ambiguous if it generates the same string in more than one way
Example: S → AB
A→a
B→b
A → ab
This grammar is ambiguous because the string "ab" can be generated in two ways: S →
AB → aB → ab, and S → AB → A → ab.
