Appendix B
FREQUENTLY ASKED UNIVERSITY QUESTIONS WITH SOLUTIONS
PART A - Brief Questions
- What is the proof by contradiction?
Ans: In a proof by contradiction we assume, along with the hypotheses, the logical negation of the result we wish to prove, and then reach some kind of contradiction. Principle of Contradiction is as follows.
If we want to prove “If P, Then Q”
- We assume P and Not Q.
- We arrive at some conclusion contradicting one of our assumptions, or something obviously untrue for Not Q.
- This contradicts our assumption for P and Not Q.
- Define ε - closure(q) with an example.
Ans: Epsilon Closure of a state is simply the set of all states we can reach by following the transition function from the given state that are labeled ε. This can be expressed as either (q) or ε-closure (q).
ε-closure (q_{0}) = {q_{0}, q_{1}, q_{2}}
ε-closure (q_{1}) = {q_{1}, q_{2}}
ε-closure (q_{2}) = {q_{2}}
- Construct NFA for the regular expression a*b*.
Ans:
- Is regular set closed under complementation? Justify.
Ans: The compliment of two regular languages is regular.
If L is a regular language over alphabet Σ, then Σ*-L is also regular language.
- Specify the use of Context free grammar.
Ans:
- Construction of compilers.
- Simplified the definition of programming languages.
- Describes the arithmetic expressions with arbitrary nesting of balanced parenthesis { (, ) }.
- Describes block structure in programming languages.
- Model neural nets.
- Define parse tree with an example.
Ans: A tree is a parse \ derivation tree for G if:
- Every vertex has a label which is a symbol of VU TU{∅}.
- The label of the root is S.
- If a vertex is interior and has a label A, then A must be in V.
- If n has a label A and vertices n_{1}, n_{2}, ….. n_{k} are the sons of the vertex n in order from left with labels X_{1}, X_{2}, ………..X_{k} respectively then A→ X_{1}X_{2}…..X_{k }must be in P.
- If vertex n has label ε, then n is a leaf and is the only son of its father.
- State pumping lemma for CFL.
Ans: Let L be any CFL. Then there is a constant n, depending only on L, such that if Z is in L and |Z| > = n, then Z = UVWXY such that:
- |VX| > = 1
- |VWX| < = n and
- for all i> = 0 UV^{i}WX^{i}Y is in L.
- What is Chomsky normal Form?
Ans: A CFG is in Chomsky Normal Form (CNF) if each of its productions has one of the two forms:
- Non terminal → string of exactly two Nonterminals i.e. A → BC
- Non terminal → one terminal i.e A → a
- Mention the difference between P and NP problems.
Ans:
- P. Problems are those that can be solved by a Turing Machine (deterministic) in polynomial time. (“P” stands for polynomial). P problems are class of problems which can be solved efficiently.
- NP. Problems are those that can be solved by nondeterministic Turing machine in polynomial time. A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution).
- What is recursively enumerable language?
Ans:
- A language is said to be r.e if there exists a TM that accepts it.
- L is recursively enumerable iff there is a TM that semi-decides L. (Turing acceptable languages).
- What is meant by DFA?
Ans: Finite Automata is a mathematical model of a system consisting of finite set of states, set of transition from state to state that occurs on input symbols from alphabet. DFA has moves well defined on the current state and current input symbol. Deterministic finite automata can be defined using 5 tuple form as M = (Q, ∑, δ, q_{0}, F)
Where Q = Non empty finite set of states
∑ = input alphabet
q_{0 } = initial start state
F = set of final states
δ = transition function that takes two arguments a state and input symbol and returns output as state i.e δ: Q X Σ → Q
Ex: δ(q_{1}, a) = q_{2}
- Define the term Epsilon transition.
Ans: Epsilon Closure of a state is simply the set of all states we can reach by following the transition function from the given state that are labeled ε. This can be expressed as either (q) or ε-closure (q).
- What is a regular expression?
Ans: Regular Expression describes the language accepted by finite state automata. The basic operations performed on regular expressions are union, concatenation and Kleene’s closure. Among the three, closure has highest precedence, next highest is for Concatenation and least is for union.
Example: an identifier in any high level language is given by R.E
An identifier starts with a letter followed by any number of letters or digits. The regular expression can be given as l(l|d)*.
- Name any four closure properties of Regular languages.
Ans: The principal closure properties of regular languages are:
- The union of two regular languages is regular.
If L and M are regular languages, then so is L ∪ M.
- The intersection of two regular languages is regular.
If L and M are regular languages, then so is L ∩ M.
- The compliment of two regular languages is regular.
If L is a regular language over alphabet Σ, then Σ*-L is also regular language.
- The difference of two regular languages is regular.
If L and M are regular languages, then so is L − M.
- The union of two regular languages is regular.
- What is a CFG?
Ans: A context free grammar (CFG) is denoted as G = (V, T, P, S) where V and T are finite set of variables and terminals respectively. V and T are disjoint. P is a finite set of productions each is of the form A->α where A is a variable and α is a string of symbols from (V U T)*.
- Define the term Ambiguity in grammars.
Ans: A grammar is said to be ambiguous if it has more than one derivation trees for a sentence or in other words if it has more than one leftmost derivation or more than one rightmost derivation.
- What is meant by Greibach Normal Form?
Ans: A context free language is said to be in Greibach Normal Form if all productions are of the form A→ aα, where a ∈ T and α ∈ V*.
- List the closure properties of Context Free Languages.
Ans: CFL’s are closed under union, concatenation, closure. These languages are not closed under intersection and compliment. If the context free languages are deterministic then they are closed even under intersection.
- What is meant by recursively enumerable language?
Ans: The language for which the Turing machine halts for the words of the language and may or may not halt for the words that are not in the language is said to be a recursively enumerable language.
- Define the class NP problem.
Ans: NP. Problems are those that can be solved by nondeterministic Turing machine in polynomial time. A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution). NP problems are class of problems which cannot be solved efficiently.
- Draw the transition diagram (automata) for an identifier.
Ans: Identifier is a token which has a pattern “An alphabet followed by any number of alphanumeric characters”. The corresponding regular expression is
[A-Za-z] [A-Za-z0-9]*.When the expression is specified using regular expression then the corresponding Finite automata generated is as
- What is a non deterministic finite automation?
Ans: Nondeterministic finite automata can be defined as quintuple M = (Q, ∑, δ, q_{0}, F)
Where Q = Non empty finite set of states
∑ = input alphabet
q_{0 } = initial start state
F = set of final states
δ = transition function that takes two arguments a state and input symbol and returns output as state i.e δ: Q X ∑ →2^{Q}
- State pumping lemma for regular languages.
Ans: If L is a Regular Language represented with automaton with maximum of n states, then there is a word in L such that the length |Z| ≥ n, we may write Z = UVW in such a way that |UV| ≤ n, |V| ≥ 1, and for all i ≥ 0, UV^{i}W is in L.
- Construct NFA equivalent to the regular expression: (0 + 1)*01.
Ans: We can have any string on 0 or 1 but should end with 0 followed by 1.
- Write the CFG for the language L = {a^{n} b^{n} | n ≥ 1}.
Ans: The Given language is a^{n}(bb)^{n }where n is greater than or equal to 1. It implies the language contains strings of the form {ab, aabb, aaabbb, …….}. Hence it can be defined as
S → aSb | ab - Compare NFA and PDA.
Ans: NFA is Non – deterministic Automata and has moves well defined on the current state and current input symbol and has no storage. The language accepted by NFA is Regular Language and is defined as N = {Q, ∑, δ, q_{0}, F}where strings are as {w | (q_{0}, w) q_{f}} i.e it reaches to at least one final state in the resultant
PDA is push down Automata and has moves well defined on the current state, current input symbol and element present on top of the stack. The language accepted by PDA is Context Free Language and is defined as P = {Q, ∑, Γ, δ, q_{0}, Z_{0}, F}where strings are as {w | (q_{0}, w, Z_{0}) (q_{f}, ε, Z_{0})} i.e it reaches to at least one final state.
- What are the closure properties of CFL?
Ans: CFL’s are closed under Union, Concatenation, closure, substitution, homomorphism. CFL’s are not closed under intersection and complement.
- List out the different techniques for Turing machine construction.
Ans: The different techniques for Turing machines are
- Storage in Finite Control
- Check off symbol
- Shifting over
- Multi track tape
- Subroutine
- What are (a) recursively enumerable languages (b) recursive sets?
Ans:
- A language is said to be r.e if there exists a TM that accepts it.
- L is recursively enumerable iff there is a TM that semi-decides L. (Turing acceptable languages). Recursive sets consists set of strings that are accepted by the Turing machine.
- What is Universal Turing machines?
Ans: A universal Turing machine, M_{u} is an automata that, given as input the description of any Turing machine M and a string w, can simulate the computation of M for input w. To construct such an M_{u} we first choose a standard way of describing Turing machines. We may, without loss of generality, assume that M = (Q, {0, 1}, {0, 1, B}, δ, q_{1}, B, q_{2}) where
Q = {q_{1}, q_{2}, ………………q_{n}} and q_{1} the initial state, q_{2 }the single final state. The alphabet {0, 1, B} ∈ Γ are represented as a_{1}, a_{2} and a_{3}. The direction left and right are represented as D_{1} and D_{2} respectively. The transitions of TM are encoded in special binary representation where each symbol is separated by 1.
- Construct deterministic finite automata to recognize odd number of 1’s and even number of 0’s?
Ans:
- State the relations among regular expression, deterministic infinite automaton, non deterministic finite automaton and finite automaton with epsilon transition.
NFA – Non deterministic Finite Automata.
DFA – Deterministic Finite Automata.
- Let L = {w: w ∈ {0, 1}* w does not contain 00 and is not empty}. Construct a regular expression that generates L.
Ans: Given: L = {w: w ∈ {0, 1} * w does not contain 00 and is not empty}
Solution:
RE = 1*01*
- Prove or disprove that the regular languages are closed under concatenation and complement.
Ans: Concatenation: Let A = (Q, Σ, δ, q_{0}, F) where
Q = Q_{1} ∪ Q_{2}, Σ = Σ_{1} ∪ Σ_{2}, q_{0} = q_{1}, F = F_{2} and δ is defined as follows:
δ(q, a) = {δ_{1} (q, a)} for each q in Q_{1}−F_{1}
δ(q, a) = {δ_{1} (q, a)} for each q in F_{1 }
and
δ(q, a) = {δ_{2} (q, a)} for each q in Q_{2}.
A word w is in L_{1} L_{2} if w = w_{1} w_{2} where w_{1} ∈ L_{1} and w_{2} ∈ L_{2}.
This is equivalent to δ_{1}(q_{1}, w_{1}) being F_{1} and δ_{2}(q_{2}, w_{2}) being F_{2} which is equivalent to w_{1} w_{2} being in T(A). Thus L_{1} L_{2} = T(A).
Theorem
The class of regular sets is closed under complementation. That is if X is a regular set and X ⊆ Σ*–L is a regular set.
Proof
Let X be X(M) for DFA M = (Q, Σ_{1}, δ, q_{0}, F) and let X ⊆ Σ*. First we assume Σ_{1} = Σ, if there are symbols in Σ_{1} not in Σ, we may delete all transitions of M on symbols not in Σ. The fact that X ⊆ Σ* assures us that we shall not thereby change the language of M. If there are symbols in Σ not in Σ_{1}, then none of these symbols appear in words of X. We may therefore introduce a dead state d into M with δ(d, a) = d for all in Σ and δ(a, a) = d for all q in Q and a in Σ − Σ_{1}. Now to accept Σ*−X, complement the final states of M. That is let M′ = (Q, Σ, δ, q_{0}, Q−F).
The M′ accepts a word w if and only if is in Q−F, that is, w is in Σ*−X. Note that it is essential to the proof that M is deterministic and without y moves.
- Consider the following grammar G with productions
S→ABC|BaB A→aA|BaC | aaa B→bBb|a C → CA| AC
Give a CFG with no useless variables that generates the same language.
Ans: The variables A and B are generating and derives a terminal string. Therefore C is a useless variable. After removing ‘C’, the CFG is:
S→BaBA→aA|aaaB→bBb|a - State the definition for Pushdown automata.
Ans: A push down automaton M is defined by (Q, Σ, Γ, δ, q_{0}, z_{0}, F), where
- Q is a finite set of states.
- Σ is an alphabet called the input alphabet – is a finite alphabet of tape symbols.
- Γ is an alphabet called stack alphabet – is a finite alphabet of stack symbols.
- q_{0} ∈ Q is the start state (or) initial state
- z_{0} in Γ is a particular stack symbol called start symbol.
- F⊆Q is the set of final (or) favorable states.
- δ is the transition relation.
i.e. δ is a subset of (Q × (Σ∪{e}) × Γ*) → (2^{Q}^{×Γ}^{*}) - Convert the following grammer G in greibach normal form.
S→ABb|a A → aaA | B B → bAb
Ans: GNF (Solution):
Replace S with A_{1}, A with A_{2} and B with A_{3}.
A_{1} → A_{2} A_{3}b | aA_{2} → aaA_{2} → A_{3}^{ }A3 → b A_{2}bHere A_{2} and A_{3} are useless symbols. Therefore the required GNF form is:
A_{1} → a - Design a Turing machine with no more than three states that accepts the language.
a(a + b)*. Assume ∑ = {a, b}.
Ans: TM for the language L = a(a + b)*
(i.e.) {a, aa, ab, aab, abb ⊃ } - State Rice’s theorem.
Ans: Any nontrivial property about the language recognized by a Turing maching is undecidable.
A property about Turing machines can be represented as the language of all Turing Machines, encoded as strings, that satisfy that property. The property P is about the language recognized by Turing machines if whenever L(M) = L(N) then P contains (the encoding of) M iff it contains (the encoding of) N. The property is non-trivial if there is at least one Turing Machine that has the property, and at least one that hasn’t.
- Show that the collection of all Turing machines is countable.
Ans: First, observe that the set of all strings in Σ is countable for any alphabet. We create a listing of the strings by writing down all strings of length 1, followed by all strings of length 2, etc. Since each TM can be described by a finite string we can list all TM’s by listing only those strings in Σ that correspond to valid TM representations.
- What do you mean be expressive power of a grammar?
Ans: Expressive power of a grammar is a measure of how concisely grammar can be expressed in a particular formalism by introducing the set of rules. In original motivation grammar was the description of language and comparison of various terminologies from the literature with respect to expressiveness.
- Construct a PDA to accept the language {(ab)^{n} |
n ≥ 1} empty stack.
Ans: L = {ab; abab, ababab…}
δ(q_{0}, a, z_{0}) = (q_{1}, az_{0})δ(q_{1}, b, a) = (q_{0}, ∅)δ(q_{0}, λ, z_{0}) = (q_{2}, λ) - When does a Turing machine become an algorithm?
Ans: If a TM decides a language or computes a function it can be reasonably thought of as an algorithm that performs correctly and reliably some computational task.
- Give a semi-Thue grammar generating (a^{i}|i is a positive power of 2).
Ans: Give a semi-The grammar generating {a^{i}| i is a positive power of 2).
S→ACaB, Ca→aaC, CB→DB, CB→E, aD→Da,AD→AC, aE→Ea, AE→ε - What is {10, 11}* (Write atleast first seven terms)
Ans: (ε, 10, 11, 1011, 101011, 101111, 111110, …)
- State Greback Normal From.
Ans: A context free grammar G is in GNF if every production is of the form A→aa where α∈N* and a∈T (α may be λ) and S→λ is in G if λ ∈ L(G), where S does not appear on the RHS of any production.
- For a PDA M = (Q, Σ, ϒ, δ, q_{0}, Z_{0}, F), define the language accepted by final state.
Ans: Let M = (Q, ∑, ∈, δ, q_{0}, Z_{0}, F) be a PDA. Then, the language accepted by M is the set of strings such that
L(M) = (w | q0, w, z0) | −(P, ε, γ), P ∈ F, γ ∈ Γ*). i.e., PDA M consumes w from the input and enters an accepting state.
- When do you say a problem is NP-Hard?
Ans: It is obvious the P ⊆ NP. It is not known that whether there exists some language L in NP, which is also accepted by deterministic TM.
A language L is said to be NP-hard if L_{1} ≤ PL for every L_{1} ⊆ NP. The language L is NP-complete if L ⊆ NP and L is NP-hard.
- State pumping lemma for context-free languages.
Ans: Let L be an infinite context-free Language. Then there exists some positive integar m such that any w∈L with |w≥m can be decomposed as
w = uvxyz (1)
with
|vxy|≤m (2)
and
|vy|≥1 (3)
Such that
uv^{i}xy^{i}z ∈ L (4)
for all i = 0, 1, … This is known as pumping lemma for context free languages.
- State two languages, which are not recursively enumerable.
Ans: State two languages, which are not recursively enumerable.
- The diagonalization language L_{d} is the set of string w_{i}, where w_{i} ∉ L(M_{i})
- The language NSA (Not Self Accepting)
- List any four ways of theorem proving
Ans:
- Deductive proofs
- Proof about sets
- Proof by contradiction
- Proof by counter example
- Show that the complement of a regular language is also regular.
Ans: Let L = L(A) for the DFA A = (α, Σ, δ, q_{0}, F)
then = L(B ) where B is a DFA and B = (α, Σ, δ, q_{0}, F)
B = (α, Σ, δ, q_{0}, Q–F)
DFA B is similar h DFA A but the final states of A have become the non-final states of DFA B and the final states of DFA B have become the non-final states of DFA A.
∴ω is in L(B) iff δ*(q, ω) is in Q–F, which occurs iff ω is not in L(A)
- What is meant by equivalent states in DFA?
Ans: The states ‘p’ and ‘q’ are said to be equivalent if for all input strings ω ∈ Σ*, δ*(p, ω) is a final stae iff δ*(q, ω) is a final state.
- State pumping lemma and its advantage.
Ans: Let L be a regular language. Then there exists a constant ‘n’, the number of states that accepts L such that if z is any string in L and z can be written as such that z = μνω in a way
|μν| ≤ n
|ν| ≥ 1 and
for all i ≥ 0, μν^{i} ∈ ΣThe pumping language is used to check whether the certain language is regular or not.
- Consider the alphabet Σ = (a, b, (, ), + , *, · ∅) construct a CFG that generates all strings in Σ* that are regular expressions over the alphabet {a, b}.
Ans: E → E + E | E*E | E·E | (E) | a | b | ∈
- Find whether the language {a^{m}, b^{m}, c^{m}/m ≥{0} is CFL or not.
Ans: Let z = a^{n}b^{n}c^{n}
Then |z| = |a^{n}b^{n}c^{n}| = 3^{n}
Let ‘n’ be the number defined in pumping lemma.
|z| = 3^{n} >n
As 0 ≤ |νx| ≤ n, ‘ν’ or ‘x’ cannot contain all the three symbols of a, b, c So, ‘ν’ or ‘x’ is of the form
- a’s
- b’s
- c’s
- a^{i}b^{i}
- b^{i}c^{i}
Then uv^{i}ux^{i}y
Let i = 0, u = a^{i}, v = b^{j }z = uv^{0}wx^{c}y – uwy
∴ uwy contains atmost a^{i}, b^{n}^{-}^{j}, c^{n}, which is not of the form uv^{i} wx^{i} y
∴ uwy ∉ L
∴ L is not content free.
- Define the language recognized by the PDA using empty stack.
Ans: Let M = (μ, Σ, Π, δ, q, z, F = ɸ) be a PDA, then the language accepted by empty stack or null stack is denoted by N(M) defined as
N(M) = {w/(q, w, z) (p, ∈, e) ɸ∧ (p, ∈, z) for sum p in a}
- What is meant by multitape Turing Maching?
Ans: A multitape Turing Machine has a finite control with some finite number of tapes. Each tape is infinite in both direction. It has its own initial state and some final states.
- What are useless symbols in a grammar?
Ans: A symbol X is said to be useful if there is a derivation such that
Sα × βω,for some α, β, ∈ (VUT)*w ∈T*
otherwise X is said to be useless.
- Define diagonal language
Ans: The language L_{d} consists of all those strings ‘w’ such that the Turing Machine represented by ‘w’ does not accept the input ‘w’
L_{d} = {w_{c}w_{c }∉ L(M_{i})} - What is a finite automation? Give the examples.
Ans: A finite automation (FA) is a mathematical model/computational model of a system with discrete inputs and outputs. It consists of a finite set of states and set of transitional from one state to another state that depends in input symbols.
E.g.,
- Control mechanism of Elevator
- Working Principle of Digital Logic Circuit.
- Operation of washing Machine.
- Enumerate the differences between DFA and NFA.
Ans:
DFANDFAThe future/behaviour of the system can be determined uniquely.
The future/behaviour of the system can’t be determined uniquely
δ : Q × Σ → Cα
δ : Cα × Σ → 2^{Cα}
δ(q,a) = p ∀a ∈ Σ
δ(q,a) = {p} ∀a ∈ Σ
∀q,p ∈ Cα
∀p,q ∈ Cα
Results in a single state on leading an input symbol
Results in a multiple state on leading an input symbol
- Verify whether L = a^{2n} / n ≥ I} is regular.
Ans:
- Assume that L is regular.
Let ‘n’ be the number of states in FA accepting L.
- Let z = a^{2}^{n}.
Then |Z| = 2x > x
By PL, z = uvw with |uv| ≤ x & |v| > 0
- Let I = 2 is uv^{i}w
Then |uv^{2}w| = |uvw.v|
= 2x + x= 3x ≠ 2xi.e., ‘a’ increases is proves of 2x not in 3x
∴ uv^{2}w ∈ L, which is a contradiction.
Hence L is not regular.
- Assume that L is regular.
- Mention the closure properties of regular languages.
Ans:
- Union
- Intersection
- Complement
- Difference
- Reversal
- Closure
- Let the properties of a grammar be S → OB|1A; A → O|OS|1AA, B → 1|1S| OAA. For the string 0110, find a right most deviation.
Ans:
- Define the languages generated by a PDA Using the two method of accepting a language.
Ans: Let M = (Q, Σ, Г, δ, q_{e}, Z_{0}F) be a PDA. Then the language accepted by a final store is denoted by L(M), defined as
L(M) = {ω/(q_{0}, ω, z_{0}) (P, ∈, v) for serve P ∈ F, v ∈ Г^{*}}
Let M = (Q, Σ, Г, δ, q_{0}, Z_{e}, F = ɸ) be PDA. Then the language accepted by a empty stack/null stack is denoted by N(M), is defined as,
N(M) = {ω/(q_{0}, ω, z_{0}) (P, ∈, ∈) / (P, ∈, Z_{0}) for serve P ∈ Q}
- State pumping lamina for content-free language.
Ans: Let L be any central free language. Then there is a constant ‘n’ depending on ‘L’ bench that Y Z is in L and Z| ≥ x , then z = uvuxy such that
|vx| ≥ I|vωx| ≤ xFor all i ≥ 0, uv^{i}wx^{i}y ∈ L
- Define a Turning Machine.
Ans: A Turning Machine M = (α, Σ, Г, δ, q_{0}, B_{1}F)
Where
Q - finite set of states.
Г - set of tape symbols, tape alphabet
Σ - set of input symbols, input alphabet
q_{0} ∈ cα the initial state
B ∈ Г called black symbol.
F ≤ cα the set of final state
δ is a partial function (transition function) mapping from Q × Г to finite sets or Q × Г × {L, R}
i.e. f : Q × Г → finite subsets q Q × Г × {L, R} where L – Left direction R – Right direction.
- Differentiate between recursive and recursively enumerate languages.
Ans:
RecursiveRecursively EnumerateA language is recursive if there exists a Tuning Machine M that accepts L and goes to halt state or else rejects L.
A language is recursively enumerable (RE) if there exists a Tuning Machine that accepts every string of L and does not accepts strings that are not in the language.
- Mention any two undesirability properties of recursively enumerable languages.
Ans:
- Emptiness
- Finiteness
- Regularity
- Content free.
PART B - Detailed Questions
- Prove by induction on n that
Ans: Many theorems are proved by mathematical induction. Suppose we have a statement P(n) about a non negative integer n. A commonly chosen example is to take P(n) to be
The principle of mathematical induction is that P(n) follows from
- P(0) and
- P(n-1) implies P(n) for N ≥ 1
condition (a) is an inductive proof, called the ‘basis’.
condition (b) is called the inductive step.
The L.H.S of (b) that is P(n-1) is called the inductive hypothesis.
Ex:
Basis of induction:
n = 1 than L.H.S = 1
R.H.S = n(n + 1)/2 = 2/2 = 1
Induction hypothesis:
We assume n = k. Then equation becomes
1 + 2 + 3 + …………….. + K = K(K + 1)/2
Inductive step: We assume that equation is true for n = k. And then check if it is also true for n = K + 1 or not.
L.H.S = 1 + 2 + 3…………K + (K + 1)
- Construct a DFA accepting binary strings such that the third symbol from the right end is 1.
Ans: Since third symbol from right end is 1, we can have minimum 4 states.
The first transition should be on 1, remaining can be either 0 or 1.
- Every language that can be described by NFA can be described by some DFA
- DFA in practice has more states than NFA
- Equivalent DFA can have at most 2^{n} states where as NFA has only n states.
- Construct NFA without ε - transitions for the NFA given below.
Ans: The transition table is
Step 1: Find ε-closure of each state.
ε-closure (q_{0}) = {q_{0}, q_{1}}ε-closure (q_{1}) = {q_{1}}Step 2: Find the transition on each state for each element.
(q_{0}, 0) = ε-closure (δ(ε-closure (q_{0}), 0))= ε-closure (δ({q_{0}, q_{1} }, 0))= ε-closure ({q_{0}}, ∪{∅})= {q_{0}, q_{1} }(q_{0}, 1) = ε-closure (δ(ε-closure (q_{0}), 1))= ε-closure (δ({q_{0}, q_{1} }, 1))= ε-closure ({∅ }, ∪{ q_{1}})= { q_{1} }(q_{1}, 0) = ε-closure (δ(ε-closure (q_{1}), 0))= ε-closure (δ({q_{1} }, 0))= ε-closure ({∅})= { ∅ }(q_{1}, 1) = ε-closure (δ(ε-closure (q_{1}), 1))= ε-closure (δ({q_{1} }, 1))= ε-closure ({ q_{1}})= { q_{1}}NFA without – ε transitions is
a=0a=1→*q0{q_{0}, q_{1} }{q_{1}}*q_{1}∅{q_{1}} - Construct NFA accepting binary strings with two consecutive 0’s.
Ans: The language has strings of the form {00, 000, 100, 001, 1100, 0011, 0000…}
On two consecutive 0’s go to state D using A. In A state and D state define moves to be in the same state on 0/1 as shown in the figure.
- Obtain minimized finite automata for the regular expression (b/a)*baa.
Ans: The strings accepted are ending with baa. The NFA for it can be drawn as follows.
The DFA for it is as shown in the following figure
Minimization of the DFA
Let us represent the DFA as transition table.
a=aa=b→q_{1}q_{1}q_{2}q_{2}q_{3}q_{2}q_{3}q_{4}q_{2}*q_{4}q_{1}q_{2}- Initially we identify 0 – equivalence as ∏_{0} = {Q_{1}^{0}, Q_{2}^{0}} Where Q_{1}^{0 }is set of final states & Q_{2}^{0} = Q − Q_{1}^{0 }is set of non final states.
Q_{1}^{0 } = {q_{4}}
Q_{2}^{0 } = {q_{1}, q_{2}, q_{3}}
- Construct ∏_{1 }from ∏_{0} identifying the equivalent states in { Q_{1}^{0}, Q_{2}^{0}}
Q_{1}^{0 }cannot be divided as it has only one state.
Q_{2}^{0 }has four states, we need to identify whether they are 1- equivalent.
Compare q_{1}, q_{2} on input a and b
δ (q_{1}, a) = q_{1}
δ (q_{2}, a) = q_{3} both resultant states belong to Q_{2}^{0}.
δ(q_{1}, b) = q_{2}
δ(q_{2}, b) = q_{2} both resultant states belong to Q_{2}^{0}.
⇒ q_{1 }is 1- equivalent to q_{2 }
Compare q_{1}, q_{3} on input a and b
δ(q_{1}, a) = q_{1}
δ(q_{3}, a) = q_{4} both resultant states belong to different sets in Π_{0}.
δ(q_{1}, b) = q_{2}
δ(q_{3}, b) = q_{2} both resultant states belong to Q_{2}^{0}.
⇒ q_{1 }is not 1- equivalent to q_{3}
∴∏_{1} = {Q_{1}^{1}, Q_{2}^{1}, Q_{3}^{1}}
Where
Q_{1}^{1 } = { q_{4}}
Q_{2}^{1 } = { q_{1}, q_{2 }}
Q_{3}^{1 } = { q_{3}}
- Construct ∏ _{2 }from ∏ _{1} identifying the equivalent states in {Q_{1}^{1}, Q_{2}^{1}, Q_{3}^{1}}
Q_{1}^{1 }and Q_{3}^{1 }cannot be divided as these have only one state.
Q_{2}^{1 }has two states, we need to identify whether they are equivalent.
Compare q_{1}, q_{2} on input a and b
δ(q_{1}, a) = q_{1}
δ(q_{2}, a) = q_{3} both resultant states belong to different sets in Π_{1}.
δ(q_{1}, b) = q_{2}
δ(q_{2}, b) = q_{2} both resultant states belong to Q_{2}^{0}.
⇒ q_{1 }is not 2- equivalent to q_{2 }
∴∏_{2} = {Q_{1}^{2}, Q_{2}^{2}, Q_{3}^{2}, Q_{4}^{2} }
Where
Q_{1}^{2 } = { q_{4}}
Q_{2}^{2 } = { q_{1 }}
Q_{3}^{2 } = { q_{2}}
Q_{3}^{2 } = { q_{3}}
- We see that ∏_{2} is equal not equal to ∏_{1}, and each set has only single state
a=aa=b→q_{1}q_{1}q_{2}q_{2}q_{3}q_{2}q_{3}q_{4}q_{2}*q_{4}q_{1}q_{2}
- Initially we identify 0 – equivalence as ∏_{0} = {Q_{1}^{0}, Q_{2}^{0}} Where Q_{1}^{0 }is set of final states & Q_{2}^{0} = Q − Q_{1}^{0 }is set of non final states.
- Prove that there exists NFA with ε- transition that accepts the regular expression y.
Ans: This statement can be proved by mathematical induction.
To show that it is true let k = ∅. The corresponding FA can be showed as follows.
Let k = 0. The string with length 0 is ε and its corresponding FA is shown in table \
Let k = 1. The string of length 1 in Σ defined as {a, b} is either a or b and its corresponding FA is shown in table
Let us assume that it is true for all k = 2, 3, 4, …..i-1. To show that it is true for k = i there are three possible operations applied on regular expression which has corresponding FA.
Case 1:
Let r_{1} and r_{2} be two regular expressions with less than i operations that has FA M_{1} and M_{2} given as M_{1} = {Q_{1}, Σ_{1}, δ_{1}, q_{1}, {f_{1} }} and M_{2} = {Q_{2}, Σ_{2}, δ_{2}, q_{2}, {f_{2} }} To show that r formed using union operation as r = r_{1} + r_{2} has automaton M which accepts the language L(M_{1}) U L(M_{2}) and is shown below.
M = {{Q_{1} U Q_{2} U {q_{0}, f_{0}}}, { Σ_{2} U Σ_{2}}, δ, q_{0}, {f_{0}} } where δ is defined as
- δ(q_{0}, ε) = { q_{1}, q_{2} }
- δ(q, a) = δ_{1}(q, a) for q in Q_{1} –{f_{1}} and a in Σ_{1} U {ε}.
- δ(q, a) = δ_{2}(q, a) for q in Q_{2} –{f_{2}} and a in Σ_{2} U {ε}.
- δ(f_{1}, a) = δ_{2}(f_{2}, a) = {f_{0}}
By inductive hypothesis there are no transitions out of the final states. Thus all moves of M_{1} and M_{2} are present in M. Any string x valid in M_{1} or M_{2} must be valid in M. For such a string there exists a path from q_{0} to f_{0}. To prove this observe rule 1 which shows path from q_{0} to either q_{1} or q_{2}. Since “x” is valid in either M_{1} or in M_{2} there exists path from q_{1} to f_{1} or from q_{2} to f_{2}. By rule 2 and 3 all these transitions are also present in M. By rule there is a path from f_{1} and f_{2} to f_{0}. Hence there is path from initial state to final state which indicates “x” is also valid in M.
Case 2:
Let r_{1} and r_{2} be two regular expressions with less than i operations that has FA M_{1} and M_{2} given as M_{1} = {Q_{1}, Σ_{1}, δ_{1}, q_{1}, {f_{1} }} and M_{2} = {Q_{2}, Σ_{2}, δ_{2}, q_{2}, {f_{2} }} To show that r formed using concatenation operation as r = r_{1} ∙ r_{2} has automaton M which accepts the language L(M_{1}) ∙ L(M_{2}) as shown below.
M = { {Q_{1} U Q_{2} }, { Σ_{1} U Σ_{2}}, δ, q_{1}, {f_{2}} } where δ is defined as
- δ(q, a) = δ_{1}(q, a) for q in Q_{1} –{f_{1}} and a in Σ_{1} U {ε}.
- δ(f_{1}, ε) = {q_{2}}
- δ(q, a) = δ_{2}(q, a) for q in Q_{2} and a in Σ_{2} U {ε}.
The construction of M is as shown in the figure. Any string w = xy is valid if x is in M1 and y is in M2. For such a string there exists a path from q_{1} to f_{2} where q_{1} is initial state and f_{2} is final state in M. To prove this observe rule 1 which shows path from q_{1} to f_{1} on “x” as is valid in M_{1} By rule 2 there is path from f_{1} to q_{2} on ε. Rule 3 includes path from q_{2} to f_{2} on string “y” Hence there is path from initial state q_{1} to final state f_{2} which is the concatenated string “x” and “y”. Since w = x.y, w is valid string in M.
Case 3:
Let r_{1} regular expression with less than i operations that has FA M_{1} given as M_{1} = {Q_{1}, Σ_{1}, δ_{1}, q_{1}, {f_{1} }}. To show that r formed using concatenation operation as r = r_{1}^{*} has automaton M which accepts the language L(M_{1})^{ *} as shown below.
M = {{Q_{1} U {q_{0}, f_{0}}}, Σ_{1}, δ, q_{0}, {f_{0}}} where δ is defined as
- δ(q_{0}, ε) = δ(f_{1}, ε) = { q_{1}, f_{0}}
- δ(q, a) = δ_{1}(q, a) for q in Q_{1} –{f_{1}} and a in Σ_{1} U {ε}.
The construction of M is as shown in the figure. Any string w = {ε, x, xx, }is valid if x is in M_{1} For such a strings there exists a path from q_{0} to f_{0} . If string is ε then there is path from q_{0} to f_{0} using rule 1. For string’s x or xx the path is from q_{0} to q_{1} on ε followed by path on x from q_{1} to f_{1 }using rule 2(if the string x is repeated then followed by a path on ε from f_{0} to q_{1} to repeat the string) followed by path on ε from f_{1} to f_{0 }using rule 1. Hence L(M) = L(M_{1})^{ *}.
- Which of the following languages is regular? Justify.
- L = {a^{n}b^{m} | n, m ≥ 1 }
Ans: This language corresponds to regular expression a*b* which is regular as there exists a DFA to accept all strings of the language.
- L = {a^{n}b^{n} | n ≥ 1 }
Ans: Let us assume that the language is regular. According to Pumping lemma choose the string Z = a^{n}b^{n} where the length is 2n. Let n be the number of states such that | Z | ≥ n. Now let us represent the string Z as UVW and if the language is regular then for all i, UV^{i}W ∈ L.
To check whether it is regular or not, it is required to consider three possible cases i) where the string V is formed with only a’s or ii) with only b’s or iii) with the combination of a’s and b’s.
Case 1: V is a string such that it contains only a’s.
V = a^{x} Such that x ≥ 1.
Let i = 0, then the string formed is UW, the string would be of the form a^{n-x} b^{n } ∉ L as the number of a’s is less than the number of b’s.
Case 2: V is a string such that it contains only b’s.
V = b^{x} Such that x ≥ 1.
Let i = 0, then the string formed is UW, the string would be of the form a^{n}b^{n-x} ∉ L as the number of b’s is less than the number of a’s.
Case 3: V is a string such that it contains combination of a’s and b’s.
V = a^{x}b^{x} Such that x ≥ 1.
If i = 0, then the string formed is UW, the string would be of the form a^{n-x}b^{n-x} ∈L as the number of a’s is equal to number of b’s.
If i = 1, then the string formed is UVW, the string would be of the form a ^{n-x}a^{x}b^{x}b^{n-x} ∈ L as the number of a’s is equal to number of b’s.
Now if i = 2, then the string formed is UV^{2}W, the string would be of the form a^{n-x}a^{x}b^{x}a^{x}b^{x}b^{n-x} ∉ L , the language is defined as all a’s followed by all b’s, but the string generated is a’s followed by b’s then by a’s and then by b’s which is invalid string according to the language.
Since in all the three possible cases there exists value of i such that the string is not in L. Hence the language is not regular.
- L = {a^{n}b^{m} | n, m ≥ 1 }
- Obtain the regular expression for the finite automata.
Ans: The set of equations that can be framed are
q_{1} = q_{1} a + ε -1 q_{2} = q_{1} b + q_{2} a -2 q_{3} = q_{2} b -3 Equation 1 is in the required form to apply the Arden’s theorem.
q_{1} = q_{1 }a + εq_{1} = ε (a)*Substituting the expression of q_{1} in equation 2 we get
q_{2} = (a)*b + q_{2 }aq_{2} = (a)*b (a)*Substituting the expression of q_{2} in equation 3 we get
q_{3} = (a)*b (a)*bThe regular expression for the given DFA is (a)*b (a)*b
- Is the grammar E → E + E | E * E | id is ambiguous? Justify your answer.
Ans: LMD: for string id + id * id is
E ⇒ E + E⇒ id + E⇒ id + E * E⇒ id + id * E⇒ id + id * idRMD: for string id + id * id is
E ⇒ E * E⇒ E * id⇒ E + E * id⇒ id + id * idParse trees represented by above LMD and RMD are as follows:
As there are more than one parse tree, grammar is ambiguous.
- Find the context free language for the following grammars
- S → aSbS | bSaS | ε
Ans: The language generated by this grammar is set of all strings such that the number of a’s is equal to number of b’s.
L = {w | N_{a}(w) = N_{b}(w) }This can be proved by mathematical induction.
- S → aSb | ab
Ans: The language generated by this grammar is set of all strings such that the number of a’s is equal to number of b’s and all b’s follow a’s.
L = {a^{n}b^{n} | n ≥ 1 }This can be proved by mathematical induction.
- S → aSbS | bSaS | ε
- Construct the PDA for L = {ww^{r} | w is in (a + b)*}
Ans: Read the string w and push it on to the stack. After that read each symbol, if it matches with top of the stack pop off the symbol. When input is read completely, then if stack becomes empty, then it is successful.
The PDA can be given as follows:
Let q_{0} be initial state, q_{f} be final state and Z_{0 }be bottom of the stack.
δ(q_{0}, a, Z_{0}) = (q_{0}, aZ_{0})δ(q_{0}, b, Z_{0}) = (q_{0}, bZ_{0})δ(q_{0}, a, a) = (q_{0}, aa), (q_{1}, ε)δ(q_{0}, b, b) = (q_{0}, bb), (q_{1}, ε)δ(q_{0}, a, b) = (q_{0}, ab)δ(q_{0}, b, a) = (q_{0}, ba)δ(q_{1}, a, a) = (q_{1}, ε)δ(q_{1}, b, b) = (q_{1}, ε)δ(q_{1}, ε, Z_{0}) = (q_{f}, Z_{0})The final PDA is given by M = {(q_{0}, q_{1}, q_{f}), (a, b), (a, b, Z_{0}), δ, q_{0}, Z_{0}, q_{f}}.
- Discuss the equivalence between PDA and CFG.
Ans: Suppose L is a context-free language. Then there is a PDA M such that L = N(M).
Proof: The basic idea in the construction is to build M so that it simulates the leftmost derivation of strings using G. The machine we construct uses the terminals and non-terminals of the grammar as stack symbols. What we conceptually want to do is to use the stack to hold the sentential form that evolves during a derivation. At each step, the topmost variable in the stack will get replaced by the RHS of some grammar rule. Of course, there are several problems with implementing this concept. For one, the PDA can only access the top of its stack it can’t find a variable below the top. For another, even if the PDA could find such a variable, it could not fit the RHS into a single stack slot. But these are not insurmountable. We simply have to arrange things so that the PDA always has the leftmost variable of the sentential form on top of the stack. If that can be set up, the PDA can use the technique of using extra states to push multiple symbols ‘all at once’.
The other consideration is that we are constructing a PDA, so it needs to consume the input string and give a verdict. This fits in nicely with our other requirements. In brief, the PDA will use ε-transitions to push the RHS of rules into the stack, and will use ‘normal’ transitions to consume input. In consuming input, we will be able to remove non-variables from the top of the stack, always guaranteeing that a variable is at the top of the stack.
We assume that ε is not in L(G) and let G be given as (V, T, P, S) be a context free grammar in Greibach normal form. It is required to construct M = ({q}, T, V, δ, S,Φ) where δ(q, a.A) contains (q, γ) whenever A→aγ is in P.
The PDA M simulates leftmost derivations of G. Since G is in Griebach normal form, each sentential form in a leftmost derivation consists of terminals x followed by a string of variables α. M stores the suffix α of the left sentential form on its stack after processing the prefix x. Formally we show that
S⇒xα by a leftmost derivation if and only if ( - Find GNF for the grammar
S→AA | 1
A→SS | 0
Ans:
S → AA | 1 ……..(1)A → SS | 0 ……..(2)A→ AAS | 0S_{ }| 1Apply lemma 2 for this
A→ 1S_{ }| 0 | 1S_{ }Z | 0ZZ → AS_{ }|_{ }ASZ substitute for A_{ }now in Z.
Z→ 1SS_{ }| 0S | 1SSZ | 0SZ | 1SZSZ | 1SZS_{ }| 0ZS_{ }| 0ZSZThe grammar in GNF is as follows
S → 1 | 1SA_{ }| 0A_{ }| 1SZA_{ }| 0ZSA → 1S | 0 | 1SZ | 0ZZ → 1SS_{ }| 0 S | 1SSZ | 0SZ | 1SZSZ | 1SZS | 0ZS_{ }| 0ZSZ - Explain any two higher level techniques for Turing machine construction
Ans: Storage in Finite Control
A Turing machine has a finite number of states in its CPU. However, the number of states is not always small. Like a Pentium chip we can store values in it as long as there is only finite number of states. For example all real computers have registers but there are only a fixed number of them, AND each register can only hold one of a fixed (and finite) number of bits. Similarly we define a state as a pair which stores the details of control and other stores the symbol. To account this modification we can define the turing machine as M = (Q, Σ, Г, δ, [q_{0}, B], B, F) where Q is of the form [q, a] where q is a state and a ∈ Σ, the transitions are defined as ([QX Σ], Г ) → ([QX Σ], Г,{R,L}).For example the transition δ([q,a], b) ([p, b],c,R) indicates that the control is in state q and a is stored in finite control. On the input symbol b it moves to p state and changes the symbol in finite control to b, changes the cell content as c and moves one cell right.
Multi-tape tracks
The tape is imagined as divided into cells where input to be processed is placed. We can further imagine that the tape is divided into k tracks for some finite number k as shown below.
The reading head considers k symbols each belonging to different track in same column and processes it. There are two special symbols φ and $ used in the first track which indicates the boundary of the input. The other tracks are used to place the intermediate results and the final result of the processing. The blank input is identified as the all B’s in all tracks as [B, B, B]. The input at the current position of the reading head is [1, 1, 1].
- Construct Turing machine for L = {1^{ n} 0^{ n} 1^{n} | n≥1}
Ans: The strings of 1’s followed by 0’s and followed by 1’s with number of 1’s, 0’s and 1’s are equal.
To design this we need 7 states as procedure is similar to {1^{n}0^{n} | n ≥ 0} with extra state added to take care of number of 1’s. The corresponding transition diagram is shown below.
The transition table for the same is shown below.
- Discuss the closure properties of CFL’s
Ans: CFLs are closed under substitution, union, concatenation, closure and positive closure, reversal homomorphism, inverse homomorphism
CFLs NOT closed under - intersection, difference, complement
- CFLs are closed under union
If L_{1 }and L_{2} are CFLs, then their union L_{1} + L_{2} is a CFL.
Let the grammar CFG_{1} defines language L_{1}. Assume that the nonterminals in CFG_{1} are S_{1}, A_{1}, B_{1}, C_{1}…… Let L_{2} is a language defined by CFG2 and its nonterminals are S_{2}, A_{2}, B_{2}, C_{2}, …..
Now CFG_{1} and CFG_{2} have nonintersecting sets of nonterminals.
We create a CFG for L_{1} + L_{2} as follows:
Include all of the nonterminals S_{1}, A_{1}, B_{1}, C_{1}, . . . and S_{2}, A_{2}, B_{2}, C_{2}, . . ..
Include all of the productions from CFG_{1} and CFG_{2}.
Create a new nonterminal S and a new production in CFG as
S→ S_{1} | S_{2}
- CFLs are closed under concatenation
If L_{1} and L_{2} are CFLs, then L_{1}L_{2} is a CFL.
Let the grammar CFG_{1} defines language L_{1}. Assume that the nonterminals in CFG_{1} are S_{1}, A_{1}, B_{1}, C_{1} ….. Let L_{2} is a language defined by CFG_{2} and its nonterminals are S_{2}, A_{2}, B_{2}, C_{2}, …..
Now CFG_{1} and CFG_{2} have nonintersecting sets of nonterminals.
We create a CFG for L_{1}L_{2} as follows:
Include all of the nonterminals S_{1}, A_{1}, B_{1}, C_{1}, ….. and S_{2}, A_{2}, B_{2}, C_{2}, . . ..
Include all of the productions from CFG_{1} and CFG_{2}.
Create a new nonterminal S and a production
S → S_{1}S_{2}
- CFLs are closed under closure
If L is a CFL, then L* is a CFL.
Since L is a CFL, by definition there is some CFG that generates L.
Suppose CFG for L has nonterminals S, A, B, C, . . … Change the nonterminal S to
S1.We create a new C CFG for L as follows:
Include all the nonterminals S_{1}, A, B, C, . . . from the CFG for L.
Include all of the productions from the CFG for L.
Add the new nonterminal S and the new production
S → S_{1}S | e
We can repeat last production
S → S_{1}S→ S_{1}S_{1}S → S_{1}S_{1}S_{1}S →S_{1}S_{1}S_{1}S_{1}S→ S_{1}S_{1}S_{1}S_{1}e → S_{1}S_{1}S_{1}S_{1}
Note that any word in L* can be generated by the new CFG. To show that any word generated by the new CFG is in L*, note that each of the S_{1} above generates a word in L. Also, there is no interaction between the different S_{1}’s.
- CFLs are not closed under intersection
Let L_{1} and L_{2} are two CFLs. Then L_{1} ∩ L_{2} maybe a CFL or may not be a CFL.
That means it is not closed under intersection.
Proof: We now will give an example showing that the intersection of two CFLs may not be a CFL. To show this, we assume that the language L_{1} = {a^{n}b^{n}a^{n}: n ≥ 1} is a non context free language. L_{1} is the set of words with some number of a’s, followed by an equal number of b’s, and ending with the same number of a’s.
Let L_{2} be generated by the following CFG:
S → XY
X → aXb |ε
Y → aY |ε
Thus, L_{2} = {a^{n}b^{n}a^{m}: n, m> = 0}, which is the set of words that have a clump of a’s, followed by a clump of b’s, and ending with another clump of a’s, where the number of a’s at the beginning is the same as the number of b’s in the middle. The number of a’s at the end of the word is arbitrary, and does not have to equal the number of a’s and b’s that come before it.
Let L_{3} be generated by the following CFG:
S → WZ
W → aW |ε
Z → bZa | e
Thus, L_{3} = {a^{i}b^{k}a^{k}: i, k> = 0}, which is the set of words that have a clump of a’s, followed by a clump of b’s, and ending with another clump of a’s, where the number of b’s in the middle is the same as the number of a’s at the end. The number of a’s at the beginning of the word is arbitrary, and does not have to equal the number of b’s and a’s that come after it.
Note that L_{2} ∩ L_{3} = L_{1}, where L_{1} = {a^{n}b^{n}a^{n}: n = 0, 1, 2, . . .}, which is a non context free language.
- CFLs are not closed under Complement
If L is a CFL, then may or may not be a CFL.
We first show that the complement of a CFL may be a CFL:
If L is regular, then is also regular. Also both L and are CFLs.
We now show that the complement of a CFL may not be a CFL by contradiction: Suppose that it is always true that if L is a CFL, then is a CFL. Suppose that L_{1} and L_{2} are CFLs. Then by our assumption, we must have that and are CFLs. Closure under union implies that is a CFL. Then by our assumption, we must have that compliment of is a CFL. But we know that compliment of = L1 ∩ L2 by DeMorgan’s Law. However, we previously showed that the intersection of two CFLs is not always a CFL, which contradicts the previous two steps. So our assumption that CFLs are always closed under complementation must not be true.
Thus, in general, we cannot say if the complement of a CFL is a CFL.
- CFLs are closed under union
- Explain undecidability with respect to post correspondence problem.
Ans: Given an alphabet S, one instance of Post’s correspondence problem of size s is a finite set of pairs of strings (gi, hi) (i = 1...s s> = 1) over the alphabet S.A solution of length n > = 1 to this instance is a sequence i1 i2 ... in of selections such that the strings gi1gi2 ... gin and hi1hi2 ... hin formed by concatenation are identical.
Width of a PCP instance is the length of the longest string in gi and hi (i = 1, 2, ..., s). Pair i is the short name for pair (gi, hi), where gi and hi are the top string and bottom string of the pair respectively. Mostly, people are interested in optimal solution, which has the shortest length over all possible solutions to an instance. The corresponding length is called optimal length. We use the word hard or difficult to describe instances whose optimal lengths are very large. For simplicity, we restrict the alphabet S to {0, 1}, and it is easy to transform other alphabets to their equivalent binary format.
To describe subclasses of Post’s Correspondence Problem, we use PCP[s] to represent the set of all PCP instances of size s, and PCP[s, w] the set of all PCP instances of size s and width w.
For convenience, we use a matrix of 2 rows and s columns to represent instances of PCP[s], where string gi is located at (i, 1) and hi at (i, 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in PCP[3, 3].
ig_{i}h_{i}11001201003100Let’s consider the result of selections of pair 1, 3, 1, 1, 3, 2, 2 accordingly. They can be shown in the following table with each selection assigned a different color. After the elimination of blanks and concatenation of strings in the top and bottom separately, it turns to:
10011001001001001100100100Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.
- Discuss the properties of recursive languages.
Ans: There are three possible outcomes of executing a Turing machine over a given input. The Turing machine may
- Halt and accept the input;
- Halt and reject the input; or
- Never halt.
A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language. Note: If a language L is recursive, then its complement L must also be recursive.
A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.)
- Explain any two undecidable problems with respect to Turing machine.
Ans: TM = {<M, w>| M is a TM, w is a string, M accepts w}
Assume a TM is decidable which halts and says accept or rejected. Let H be a machine for A Turing Machine <M, w>, H halts and accepts if M accepts w, or rejects if M fails to accept w.
i.e H(<H, w>) = {accept if M accept w.
= {reject if M does not accept w.
Construct new TM, D with H as subroutine. D calls H to find what M does when input to M is its own description <M>. i.e running a machine as its own decription. It is just like a compiler written and compiled in same language.
D gets information and complements the action.
D is defined as <M> where M is a Turing Machine.
In summary D(<M>) =When we run D with its own description <D> as input? In that case we get
D(<D>) =It is forced to do opposite to what D does. Thus neither TM D nor TM H exists.
- Discuss the difference between NP-complete and NP Hard problems.
Ans: The subject of computational complexity theory is focused on classifying problems by how hard they are. There are many different classifications depending the time taken by the problem. The following are the types of classification.
- P. Problems are those that can be solved by a Turing Machine (deterministic) in polynomial time. (“P” stands for polynomial). P problems are class of problems which can be solved efficiently.
- NP. Problems are those that can be solved by nondeterministic Turing machine in polynomial time. A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution). NP problems are class of problems which cannot be solved efficiently. NP does not stand for “non-polynomial”. There are many complexity classes that are much harder than NP.
- Undecidable. For some problems, we can prove that there is no algorithm that always solves them, no matter how much time or space is allowed. One very uninformative proof of this is based on the fact that there are as many problems as there real numbers, and only as many programs as there are integers, so there are not enough programs to solve all the problems. But we can also define explicit and useful problems which can’t be solved.
- Construct DFA to accept the language L = {w / w is of even length and begins with 11}
Ans:This automaton should accept strings that start with 11 and followed by any other elements such that the total length must be even. It should reject strings that start with 0. Hence on seeing 0 in the initial state it should enter into dead state from which there is no path to final state. After 1 it should find 1, hence in the second state on seeing 0 it should enter into dead state. Once it sees 11 it is final state and on seeing either 0 or 1 it goes to next state and comes back to this state on seeing either 0 or 1, which maintains the length to be even.
Δ /Σ01→ q_{0}Dq_{1}q_{1}Dq_{2}*q_{2}q_{3}q_{3}q_{3}q_{2}q_{2} - Write a note on NFA and compare with DFA
Ans: DFA has moves well defined on the current state and current input symbol. NFA the moves are not well defined i.e on an input it may go different set of states or there may be state change with out input symbol.
Language of DFA A = {Q, ∑, δ, q_{0}, F}is defined as {w | δ`(q_{0}, w) = P for some P in F}
Language of NFA A = {Q, ∑, δ, q_{0}, F}is defined as {w | δ`(q_{0}, w) ∩ F ≠ ∅ } i.e there is at least one final state in the resultant
- Convert the following NFA to DFA
δaB→p{p}{p, q}q{r}{r}*r{Φ}{Φ}
Ans: start with initial state, find transitions. Whenever you get new set of states, add it to set of states and find transitions on input symbols.
δAb→[p][p][pq][pq][pr][pqr]*[pr][p][pq]*[pqr][pr][pqr] - Discuss on the relation between DFA and minimal DFA.
Ans: Let M and M^{1} be two FA s over ∑. We construct a comparison table consisting of n + 1 columns where n is the no of input symbols.
- 1^{st} column consisting of pair of nodes of form (q, q^{1}) where q ∊ M & q^{1} ∊ M^{1}
- If (q, q^{1}) appears in same row of 1^{st} column then corresponding entry in a column (a ∊ ∑) is (qa, qa^{1}) where (qa, qa^{1}) are reachable from q & q^{1 }on a .
- Table is constructed by starting with pair of initial vertices q_{in}, q_{in}^{1} of M & M^{1 }. We complete construction by considering the pairs in 2^{nd} & subsequent column which are not in 1^{st} column.
- if we reach a pair (q, q^{1}) such that q is final states of M & q^{1 }is non final state of M^{1 }⇒ terminate construction and conclude that M & M^{1 }are not equivalent.
- if construction is terminated when no new element appears in second & subsequent columns which are not on 1^{st} column. Conclude that M & M^{1 }are equivalent.
- Discuss on regular expressions.
Ans: Any terminal symbol / element of ∑ is R.E
Ex: f, ∈, a in ∑
is a regular expression and denotes the empty set.
∈ is a regular expression and denotes the set {∈}.
a is a regular expression and denotes the set {a}.
- Union of two regular expressions R_{1} & R_{2} is Regular expression R. (R = R_{1} + + R_{2})
Ex: Let “a” be regular expression R_{1}
“b” be regular expression R_{2}
(a + b) is also a regular expression R having the elements {a, b}.
- Concatenation of two regular expression R_{1} & R_{2} written as R_{1} R_{2 }is also Regular Expression R (R = R_{1}. R_{2})
Ex: Let “a” be regular expression R_{1 }
“b” be regular expression R_{2}
(a.b) is also a regular expression R having the elements {ab}.
- Iteration (Closure) of a regular expression R written as R* is also a regular expression.
Let “a” be regular Expression
Then ∈, a, aa … are also regular expression.
If L is a language represented by the regular expression R then the Kleene closure of L is denoted as L^{*} and is given as
The positive closure of L, denoted L + , is the set.
- If R is a regular expression, then (R)^{*} is also a regular expression
- Regular Expression over ∑ is precisely those obtained recursively by the application of the above rules once or several times.
- Union of two regular expressions R_{1} & R_{2} is Regular expression R. (R = R_{1} + + R_{2})
- Discuss in detail about the closure properties of regular languages.
Ans: The principal closure properties of regular languages are:
- The union of two regular languages is regular. If L and M are regular languages, then so is L ∪ M.
- The intersection of two regular languages is regular. If L and M are regular languages, then so is L ∩ M.
- The compliment of two regular languages is regular. If L is a regular language over alphabet Σ, then Σ*-L is also regular language.
- The difference of two regular languages is regular. If L and M are regular languages, then so is L − M.
- The reversal of a regular language is regular. The reversal of a string means that the string is written backward, i.e. reversal of abcde is edcba. The reversal of a language is the language consisting of reversal of all its strings, i.e. if L = {001, 110} then L(R) = {100, 011}.
- The closure of a regular language is regular. If L is a regular language, then so is L*.
- The concatenation of regular languages is regular. If L and M are regular languages, then so is L M.
- The homomorphism of a regular language is regular. A homomorphism is a substitution of strings for symbol. Let the function h be defined by h(0) = a and h(1) = b then h applied to 0011 is simply aabb. If h is a homomorphism on alphabet Σ and a string of symbols w = abcd…z then h (w) = h(a)h(b)h(c) h(d)…h (z) The mathematical definition for homomorphism is h: Σ*→Γ* such that “ x, y ∈ Σ* and h(x), h(y) ∈ τ*. A homomorphism can also be applied to a language by applying it to each of strings in the language. Let L be a language over alphabet Σ, and h is a homomorphism on Σ, then h(L) = {h(w) | w is in L} The theorem can be stated as “ If L is a regular language over alphabet Σ, and h is a homomorphism on Σ, then h(L) is also regular ”.
- The inverse homomorphism of two regular languages is regular. Suppose h be a homomorphism from some alphabet Σ to strings in another alphabet T and L be a language over T then h inverse of L, h′ (L) is set of strings w in Σ* such that h(w) is in L. The theorem states that “If h is a homomorphism from alphabet Σ to alphabet T, and L is regular language on T, then h′(L) is also a regular language.
- Prove that the following languages are not regular
(a) {0^{2n} / n ≥ 1}
(b) {a^{m} b^{n} a^{m} + ^{n} / m ≥ 1 and n ≥ 1 }
Ans: a) The given language can be represented as set of all strings whose length is even. We can construct a finite automaton for the given language. Since the language consists of strings {aa, aaaa, aaaaaa, , ……..} where the number of a’s is even. To accept even strings whose length is greater than or equal to 2 we need three states q_{0}, q_{1 }and q_{2} where q_{0} is initial state and q_{2 }is final state. Since there exists a finite automaton we can conclude that the given language is Regular.
(b) {a^{m} b^{v} a^{m} + ^{n} / m ≥ 1 and n ≥ 1 }
Ans: Let us assume that the language is regular. According to Pumping lemma choose the string Z = a^{m}b^{n}a^{m+n} where the length is 2(m + n). Let n be the number of states such that | Z | ≥ n. Now let us represent the string Z as UVW and if the language is regular then for all i, UV^{i}W ∈ L.
To check whether it is regular or not, it is required to consider three possible cases i) where the string V is formed with only a’s or ii) with only b’s or iii) with the combination of a’s and b’s.
Case 1: V is a string such that it contains only a’s.
V = a^{x} Such that x ≥ 1.
Let i = 0, then the string formed is UW, the string would be of the form a^{m−x}b^{n}a^{n+m } L as the number of a’s and b’s is less than the number of a’s appearing after b’s.
Case 2: V is a string such that it contains only b’s.
V = b^{x} Such that x ≥ 1.
Let i = 0, then the string formed is UW, the string would be of the form a^{m}b^{n−x}a^{m+n } L as the number of a’s and b’s is less than the number of a’s appearing after b’s
Case 3: V is a string such that it contains combination of a’s and b’s.
V = a^{x}b^{x} Such that x ≥ 1.
If i = 0, then the string formed is UW, the string would be of the form a^{m−x}b^{n−x}a^{m+n} ∈ L as the number of a’s and b’s is not equal to number of a’s appearing after b’s.
If i = 1, then the string formed is UVW, the string would be of the form a^{m−x}b^{n−x} a^{m+ n } ∈ L as the number of a’s and b’s is equal to number of a’s.
Now if i = 2, then the string formed is UV^{2}W, the string would be of the form a^{n−x}a^{x}b^{x}a^{x}b^{x}b^{n−x}a^{m+n} ∉ L, the language is defined as all a’s followed by all b’s and then by a’s, but the string generated is a’s followed by b’s then by a’s and then by b’s followed by a’s which is invalid string according to the language.
Since in all the three possible cases there exists value of i such that the string is not in L. Hence the language is not regular.
- Discuss on equivalence and minimization of automata.
Ans: For any given Deterministic Automation with more number of states we can construct its equivalent DFA with minimum number of states. To minimize the automata we construct equivalence classes using the following procedure.
- Initially construct 0 – equivalence class as Π_{0} = { Q_{1}^{0}, Q_{2}^{0} } Where Q_{1}^{0 }is set of final states & Q_{2}^{0} = Q − Q_{1}^{0 }is set of non final states.
- Construct Π_{K} + _{1 }from Π_{K }further partitioning as follows:
- Let Q_{1}^{K }be any subset in Π_{K . }if q_{1 }&_{ }q_{2} are in Q_{1}^{K} they are (K + 1) equivalent provided δ(q_{1}, a) & δ(q_{2}, a) are K – equivalent.
- Find out whether δ(q_{1}, a) and δ(q_{2}, a) are in same equivalence class in Π_{K} for every a Σ. If so, q_{1 }and_{ }q_{2 }are_{ }(k + 1) equivalence. This way Q_{i }^{k }is further divided into (K + 1) equivalence classes. Repeat this for every Q_{i }^{k} in Π_{K }to get all the elements of Π_{K }_{+}_{ 1}.
- Construct Π_{n }for^{ }n = 1, , 2, 3, … until Π_{n } = Π_{n }_{+}_{ 1.}
- For required minimum state automation, states are equivalent classes obtained finally.
- Explain about Parse trees, for the following grammar
S → aB | bA A → a | aS | bAA B → b | bS | aBB
For the string “aaabbabbba”, Find LMD, RMD and Parse tree
Ans: The following is a LMD:
S ⇒aB ⇒ aaBB⇒ aaabBB⇒ aaabbB⇒ aaabbaBB⇒ aaabbabB⇒ aaabbabbS⇒ aaabbabbbA⇒ aaabbabbbaThe following is a RMD:
S ⇒aB ⇒ aaBB⇒ aaBaBB⇒ aaBaBbS⇒ aaBaBbbA⇒ aaBaBbba⇒ aaBabbba⇒ aaaBBabbba⇒ aaaBbabbba⇒ aaabbabbba(c) Derivation tree/parse tree
- Construct PDA for the language L = {ww^{r} | w is in (a + b)*}.
Ans: Read the string w and push it on to the stack. After that read each symbol, if it matches with top of the stack pop off the symbol. When input is read completely, then if stack becomes empty, then it is successful.
The PDA can be given as follows:
Let q_{0} be initial state, q_{f} be final state and Z_{0 }be bottom of the stack.
δ(q_{0}, a, Z_{0}) = (q_{0}, aZ_{0})δ(q_{0}, b, Z_{0}) = (q_{0}, bZ_{0})δ(q_{0}, a, a) = (q_{0}, aa), (q_{1}, ε)δ(q_{0}, b, b) = (q_{0}, bb), (q_{1}, ε)δ(q_{0}, a, b) = (q_{0}, ab)δ(q_{0}, b, a) = (q_{0}, ba)δ(q_{1}, b, b) = (q_{1}, ε)δ(q_{1}, ε, Z_{0}) = (q_{f}, Z_{0})The final PDA is given by M = {(q_{0}, q_{1}, q_{f}), (a, b), (a, b, Z_{0}), δ, q_{0}, Z_{0}, q_{f}}.
- Explain in detail about equivalence of Pushdown automata and CFG.
Ans: The equivalence of PDA and CFG can be proved by showing the language accepted by PDA is the language generated by the CFG.
Suppose L is a context-free language. Then there is a PDA M such that L = N(M).
We assume that ε is not in L(G) and let G be given as (V, T, P, S) be a context free grammar in Greibach normal form. It is required to construct M = ({q}, T, V, δ, S, ) where δ(q, a.A) contains (q, γ) whenever A→aγ is in P.
The PDA M simulates leftmost derivations of G. Since G is in Griebach normal form, each sentential form in a leftmost derivation consists of terminals x followed by a string of variables α. M stores the suffix α of the left sentential form on its stack after processing the prefix x. Formally we show that
S⇒xα by a leftmost derivation if and only if ( q, x, S) (q, ε, α)
Suppose M is a PDA. Then there is a grammar G such that L(G) = L(M), i.e., L(M) is context-free.
The previous construction, spelled out in full would look messy, but is in fact quite simple. Going in the reverse direction, i.e., converting a PDA to a CFG, is more difficult. The basic idea is to consider any two states p, q of PDA M and think about what strings could be consumed in executing M from p to q. Those strings will be represented by a variable [p, a, q] in G, the grammar we are building. By design, the strings generated by [p, a, q] would be just those substrings consumed by M in going from p to q. Thus S, the start variable, will stand for all strings consumed in going from q0 to an accept state. This is clear enough, but as always for PDA’s, we must consider the stack, hence the story will be more involved; for example, we will use funky variables of the form [p, A, q], where A represents the top of the stack.
The construction goes as follows: given PDA M = {Q, Σ, τ, δ, q_{0}, Z_{0}, ∅} we will construct a grammar G such that L(G) = L(M).
To convert the PDA to CFG we use the following three rules.
R1:
The productions for start symbol S are given by
S → [q_{0}, Z_{0}, q] for each state q in Q.
For each move that pops a symbol from stack with transition as
δ (q, a, Z_{0}) = (q1, ε) induces a production as
[q, Z_{0}, q1] → a for q1 in Q.
R3:
For each move that does not pop symbol from stack with transition as δ (q, a, Z_{0}) = (q1, Z_{1}Z_{2} Z_{3}Z_{4…..}) induces a production as
[q, Z_{0}, q^{m}] → a[q1, Z_{1} q_{2 }] [q_{2}, Z_{2} q_{3 }] [q_{3}, Z_{3} q_{4 }] [q_{4}, Z_{4} q_{5 }]…[q_{m-1}, Z_{m} q^{m}_{ }] for each q^{m} in Q.
After defining all the rules apply simplification of grammar to get reduced grammar.
- Construct the following grammar in CNF
A → BCD | b B → Yc | d C → gA | c D → dB | aY → f
Ans: The grammar is said to be in CNF if all the productions have either two non terminals or a single terminal on the right side of the production.
The first production after converting to CNF the resultant productions are
A → BX_{1} | bX_{1} → CDThe second production after converting to CNF the resultant productions are
B → YX_{2} | dX_{2} → cThe third production after converting to CNF the resultant productions are
C → X_{3}A | cX_{3} → gThe fourth production after converting to CNF the resultant productions are
D → X_{4}B| aX_{4} → dAnd the last is in CNF.
The final grammar in CNF is
A → BX_{1} | bX_{1} → CDB → YX_{2} | dX_{2} → cC → X_{3}A| cX_{3} → gD → X_{4}B| aX_{4} → d - Discuss about programming techniques for turing machines
Ans: Storage in Finite Control
A Turing machine has a finite number of states in its CPU. However, the number of states is not always small. Like a Pentium chip we can store values in it as long as there is only finite number of states. For example all real computers have registers but there are only a fixed number of them, AND each register can only hold one of a fixed (and finite) number of bits. Similarly we define a state as a pair which stores the details of control and other stores the symbol. To account this modification we can define the turing machine as M = (Q, Σ , Γ, δ, [q^{0}, B], B, F) where Q is of the form [q, a] where q is a state and a ∈ Σ, the transitions are defined as ([Q X Σ], Γ) → ([Q X Σ], Γ, {R,L}). For example the transition δ([q,a], b) =([p, b],c,R) indicates that the control is in state q and a is stored in finite control. On the input symbol b it moves to p state and changes the symbol in finite control to b, changes the cell content as c and moves one cell right.
Multi-tape tracks
The tape is imagined as divided into cells where input to be processed is placed. We can further imagine that the tape is divided into k tracks for some finite number k as shown below.
The reading head considers k symbols each belonging to different track in same column and processes it. There are two special symbols Φ and $ used in the first track which indicates the boundary of the input. The other tracks are used to place the intermediate results and the final result of the processing. The blank input is identified as the all B’s in all tracks as [B, B, B]. The input at the current position of the reading head is [1, 1, 1].
Checking off symbols
This is one useful trick that can be used to visualize how TM would recognize the languages. This technique uses an extra track which indicates the symbol on the other track is processed. The languages which have repeated strings or some conditions relating to other part of string can be solved with this procedure. Such languages are listed below.
- { ww | w in Σ*}
- { ww^{R} | w in Σ*}
- { a^{i}b^{i} | i ≥ 1 }
- { a^{i}b^{j}c^{k}| i ≠ j or j ≠k }
- { wcw | w in Σ*}
For the languages mentioned above we can use the tape with two tracks where on one track we place the given input and on the other track we place either B or √. If the upper track symbol is B it indicates the symbol on lower track is not considered. If the symbol on upper track is √ it indicates that the symbol on lower track is considered.
Subroutines:
A turing machine can simulate any type of subroutine found in programming languages, including recursive procedures and any of the known parameter passing mechanisms. We can design a TM program to serve as a subroutine, which has a designated initial state and a designated return state which temporarily has to move and which will be used to effect a return to the calling routine. To design a TM to call the subroutine a new set of states are defined which are used to enter the initial state of the subroutine and return from the return state of subroutine. As an example a TM is designed to accept strings with balanced parenthesis.
- Explain about the closure properties of CFL
Ans: CFLs are closed under substitution, union, concatenation, closure and positive closure, reversal homomorphism, inverse homomorphism
CFLs NOT closed under - intersection, difference, complement
- CFLs are closed under union
If L_{1 }and L_{2} are CFLs, then their union L_{1} + L_{2} is a CFL.
Let the grammar CFG_{1} defines language L_{1}. Assume that the nonterminals in CFG_{1} are S_{1}, A_{1}, B_{1}, C_{1}…… Let L_{2} is a language defined by CFG2 and its nonterminals are S_{2}, A_{2}, B_{2}, C_{2}, …..
Now CFG_{1} and CFG_{2} have nonintersecting sets of nonterminals.
We create a CFG for L_{1} + L_{2} as follows:
Include all of the nonterminals S_{1}, A_{1}, B_{1}, C_{1}, . . . and S_{2}, A_{2}, B_{2}, C_{2}, . . ..
Include all of the productions from CFG_{1} and CFG_{2}.
Create a new nonterminal S and a new production in CFG as
S→ S_{1} | S_{2}
- CFLs are closed under concatenation
If L_{1} and L_{2} are CFLs, then L_{1}L_{2} is a CFL.
Let the grammar CFG_{1} defines language L_{1}. Assume that the nonterminals in CFG_{1} are S_{1}, A_{1}, B_{1}, C_{1} ….. Let L_{2} is a language defined by CFG_{2} and its nonterminals are S_{2}, A_{2}, B_{2}, C_{2}, …..
Now CFG_{1} and CFG_{2} have nonintersecting sets of nonterminals.
We create a CFG for L_{1}L_{2} as follows:
Include all of the nonterminals S_{1}, A_{1}, B_{1}, C_{1}, ….. and S_{2}, A_{2}, B_{2}, C_{2}, . . ..
Include all of the productions from CFG_{1} and CFG_{2}.
Create a new nonterminal S and a production
S → S_{1}S_{2}
- CFLs are closed under closure
If L is a CFL, then L* is a CFL.
Since L is a CFL, by definition there is some CFG that generates L.
Suppose CFG for L has nonterminals S, A, B, C, . . … Change the nonterminal S to
S1.We create a new C CFG for L as follows:
Include all the nonterminals S_{1}, A, B, C, . . . from the CFG for L.
Include all of the productions from the CFG for L.
Add the new nonterminal S and the new production
S → S_{1}S | ε
We can repeat last production
S → S_{1}S→ S_{1}S_{1}S → S_{1}S_{1}S_{1}S →S_{1}S_{1}S_{1}S_{1}S→ S_{1}S_{1}S_{1}S_{1}ε → S_{1}S_{1}S_{1}S_{1}
Note that any word in L* can be generated by the new CFG. To show that any word generated by the new CFG is in L*, note that each of the S_{1} above generates a word in
L. Also, there is no interaction between the different S_{1}’s.
- CFLs are not closed under intersection
Let L_{1} and L_{2} are two CFLs. Then L_{1} ∩ L_{2} maybe a CFL or may not be a CFL. That means it is not closed under intersection.
Proof: We now will give an example showing that the intersection of two CFLs may not be a CFL. To show this, we assume that the language L_{1} = {a^{n}b^{n}a^{n}: n ≥ 1} is a non context free language. L_{1} is the set of words with some number of a’s, followed by an equal number of b’s, and ending with the same number of a’s.
Let L_{2} be generated by the following CFG:
S → XYX → aXb |εY → aY | εThus, L_{2} = {a^{n}b^{n}a^{m}: n, m> = 0}, which is the set of words that have a clump of a’s, followed by a clump of b’s, and ending with another clump of a’s, where the number of a’s at the beginning is the same as the number of b’s in the middle. The number of a’s at the end of the word is arbitrary, and does not have to equal the number of a’s and b’s that come before it.
Let L_{3} be generated by the following CFG:
S → WZ
W → aW |ε
Z → bZa | e
Thus, L_{3} = {a^{i}b^{k}a^{k}: i, k> = 0}, which is the set of words that have a clump of a’s, followed by a clump of b’s, and ending with another clump of a’s, where the number of b’s in the middle is the same as the number of a’s at the end. The number of a’s at the beginning of the word is arbitrary, and does not have to equal the number of b’s and a’s that come after it.
Note that L_{2} ∩ L_{3} = L_{1}, where L_{1} = {a^{n}b^{n}a^{n}: n = 0, 1, 2, . . .}, which is a non context free language.
- CFLs are not closed under Complement
If L is a CFL, then may or may not be a CFL.
We first show that the complement of a CFL may be a CFL:
If L is regular, then is also regular. Also both L and are CFLs.
We now show that the complement of a CFL may not be a CFL by contradiction: Suppose that it is always true that if L is a CFL, then is a CFL. Suppose that and are CFLs. Then by our assumption, we must have that and are CFLs. Closure under union implies that is a CFL. Then by our assumption, we must have that compliment of is a CFL. But we know that compliment of = L_{1} ∩ L_{2} by DeMorgan’s Law. However, we previously showed that the intersection of two CFLs is not always a CFL, which contradicts the previous two steps. So our assumption that CFLs are always closed under complementation must not be true.
Thus, in general, we cannot say if the complement of a CFL is a CFL.
- CFLs are closed under union
- Explain in detail about Pumping lemma for CFL.
Ans: Let L be any context free language, Then there is a constant n, which depends only upon L, such that there exists a string Z ∈ L and | Z | ≥ n where Z = UVWXY such that
- |VX | ≥ 1
- |VWX | ≤ n and
- For all i ≥ 0 UV^{i} WX^{i} Y is in L.
The string Z can be derived by a context free grammar G. The G be a grammar which is in Chomsky Normal Form. The grammar G generates language L. For the string z, we can obtain a parse tree which derives the string Z. Then if the length of the path to Z is less than or equal to i then length of word Z is less than or equal to 2^{i}^{-}^{1. }We can prove this by induction step.
Basis: If i = 1
Let G contains the rules S → a where length of the derived string is 1. i.e i = 1. Now according to the rule the word length should be ≤ 2^{i}^{-}^{1.} i.e 2^{0} = 1. Observe that we have a word which is of length 1. Also observe that the grammar G is in Chomsky’s normal form. This language is regular since | Z | = | | = 1.
Induction step: Let w be a string which is derived by grammar G.Let k be a variable such that n = 2^{k}, |z| ≥ n then |z| >2^{k}^{-}^{1} while deriving w string we may get some nonterminals of CFG. G can be repeated for any number of times and will give the string z. If we pump the substrings to w such that the path length of its newly formed string z’(z + pumped string z’) is i and the word length of z’ is 2^{i}^{-}^{1 }then the grammar G deriving^{ }z’ is called a regular grammar. The necessary condition is that grammar G is in Chomsky’s normal form.
Let us consider a grammar
G = ({A, B, C}, {a}, {A→BC |a, B→BA|b, C→BA}, A)
i.e path length i = 3
|w| ≤ 2^{i}^{-}^{1} i.e 3 ≤ 2^{2}
If we pump s substring into w which satisfies the condition as i ≤ |w| ≤ 2^{i}^{-}^{1 }≤ n the grammar producing string w is a regular grammar.
- Explain about “A language that is Recursively Enumerable”.
Ans: There are three possible outcomes of executing a Turing machine over a given input. The Turing machine may
- Halt and accept the input;
- Halt and reject the input; or
- Never halt.
A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language.
Note: If a language L is recursive, then its complement must also be recursive.
A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.)
- Discuss on undecidable problem about Turing Machine.
Ans: TM = {<M, w>| M is a TM, w is a string, M accepts w}
Assume a TM is decidable which halts and says accept or rejected. Let H be a machine for A Turing Machine <M, w>, H halts and accepts if M accepts w, or rejects if M fails to accept w.
i.e H(<H, w>) = {accept if M accept w.
= {reject if M does not accept w.
Construct new TM, D with H as subroutine. D calls H to find what M does when input to M is its own description <M>. i.e running a machine as its own decription.
It is just like a compiler written and compiled in same language.
D gets information and complements the action.
D is defined as <M> where M is a Turing Machine.
- Runs H on input <M, <M>>.
- If H accepts it rejects, if H rejects it accepts.
In summary D(<M>) =
When we run D with its own description <D> as input? In that case we get
D(<D>) =
It is forced to do opposite to what D does. Thus neither TM D nor TM H exists.
- Explain about the PCP.
Ans: Given an alphabet S, one instance of Post’s correspondence problem of size s is a finite set of pairs of strings (g_{i}, h_{i}) (i = 1...s s> = 1) over the alphabet S. A solution of length n > = 1 to this instance is a sequence i_{1} i_{2} ... in of selections such that the strings g_{i}_{1}g_{i}_{2} ... gin and h_{i}_{1}h_{i}_{2} ... hin formed by concatenation are identical.
Width of a PCP instance is the length of the longest string in g_{i} and h_{i} (i = 1, 2, ..., s). Pair i is the short name for pair (g_{i}, h_{i}), where g_{i} and h_{i} are the top string and bottom string of the pair respectively. Mostly, people are interested in optimal solution, which has the shortest length over all possible solutions to an instance. The corresponding length is called optimal length. We use the word hard or difficult to describe instances whose optimal lengths are very large. For simplicity, we restrict the alphabet S to {0, 1}, and it is easy to transform other alphabets to their equivalent binary format.
To describe subclasses of Post’s Correspondence Problem, we use PCP[s] to represent the set of all PCP instances of size s, and PCP[s, w] the set of all PCP instances of size s and width w.
For convenience, we use a matrix of 2 rows and s columns to represent instances of PCP[s], where string g_{i} is located at (i, 1) and hi at (i, 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in PCP[3, 3].
ig_{i}h_{i}11001201003100Let’s consider the result of selections of pair 1, 3, 1, 1, 3, 2, 2 accordingly. They can be shown in the following table with each selection assigned a different color. After the elimination of blanks and concatenation of strings in the top and bottom separately, it turns to:
10011001001001001100100100Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.
- Describe the following:
- Alphabet, String, Language, Empty String.
- NFA.
- Transition Diagram.
- δ in NFA with d (Epsilon) moves
Ans:
- Alphabet, String, Language, Empty String:
Symbol is an abstract entity. It cannot be formerly defined as points in geometry.
Example: Letters, digits or special symbols like $, @, # etc.,
Alphabet Finite collection of symbols denoted by Σ .
String /word Set of symbols from alphabet
Example: 001, 110, 1111 strings from binary alphabet.
a01 is not a string from binary alphabet.
Language: Set of words formed with alphabet
Example: { 0, 1, 00, 01, 10, 11 000, …… } are the strings of the language (0 + 1) +
- NFA:
Definition 3: Nondeterministic finite automata can be defined as quintuple
M = (Q, Σ, δ, q_{0}, F)
Where Q = Non empty finite set of states
Σ = input alphabet
q_{0 } = initial start state
F = set of final states
δ = transition function that takes two arguments a state and input symbol and returns output as state i.e δ: Q X Σ →2^{Q}
- Transition Diagram
A transition graph contains
- Set of states as circlesStart state q_{o }with arrow
Final state by double circle
- A finite set of transitions (edges | labels) that show how to go from some state to other.
- Set of states as circlesStart state q_{o }with arrow
- δ in NFA with ε (Epsilon) moves:
Epsilon Closure of a state is simply the set of all states we can reach by following the transition function from the given state that are labeled ε. This can be expressed as either (q) or ε-closure (q) and contains all the states that are reachable even without any input.
- Write an algorithm to minimize a given FA
Ans: The minimization algorithm for the given FA based on Π construction is explained here.
- Initially construct 0 – equivalence class as Π_{0} = { Q_{1}^{0}, Q_{2}^{0} } Where Q_{1}^{0 }is set of final states & Q_{2}^{0} = Q − Q_{1}^{0 }is set of non final states.
- Construct Π_{K} + _{1 }from Π_{K }further partitioning as follows:
- Let Q_{1}^{K }be any subset in Π_{K}._{ }if q_{1 }&_{ }q_{2} are in Q_{1}^{K} they are (K + 1) equivalent provided δ(q_{1}, a) & δ(q_{2}, a) are K – equivalent.
- Find out whether δ(q_{1}, a) and δ(q_{2}, a) are in same equivalence class in Π_{K} for every a ∈ Σ. If so, q_{1} and q_{2} are (k + 1) equivalence. This way Q_{i }^{k }is further divided into (K + 1) equivalence classes. Repeat this for every Q_{i }^{k} in Π_{K }to get all the elements of Π_{K }_{+}_{ 1}.
- Construct Π_{n }for^{ }n = 1, 2, 3, … until Π_{n } = Π_{n }_{+}_{ 1.}
- For required minimum state automation, states are equivalent classes obtained finally.
- Minimize the following FA
S01→A0A0A3A1A2A5A2A3A4A3A0A5A4A0A6A5A1A4*A6A1A3
Ans: Any two final states are 0 – equivalent and any two non final states are also 0 – equivalent.
Π_{0} (1, 2) = {{A6}, {A0, A1, A2, A3, A4, A5}}From the above table we find A0, A1, A2, A3 and A5 are 1-equivalent and hence Π_{1} is as follows.
Π_{1} (1, 3, 4) = { {A6}{ A0, A1, A2, A3, A5} {A4} }Using the new classes we find whether they are 2-equivalent.
From the above table we find A0, A1 and A3 are 2-equivalent and A2 and A5 are 2 – equivalent. hence Π_{2} is as follows.
Π_{2} (1, 4, 5, 6) = { {A6}, {A4}, { A0, A1, A3}, {A2, A5} }Using the new classes we find whether they are 3-equivalent.
From the above table we find A0, A1 and A3 are not 3-equivalent and A2 and A5 are 3 – equivalent. hence Π_{3} is as follows.
Using the new classes we find whether they are 4-equivalent.
A2A5098144From the above table we find A2 and A5 are 4 – equivalent. hence Π_{4} is as follows.
Π_{4} (1, 4, 7, 8, 9, 10, 11) = {{A6}, {A4}, { A0 }, { A1}, { A3}, {A2 }, { A5}}
Since all the sets contain single element the minimized automata is same as given automata. That is the automata cannot be minimized.
- Design a Moore Machine to determine the residue mod 4 for each binary string treated as integer.
Ans: The integer number when it is represented as binary the residue mod 4 for each input is given below.
The constructed moore machine is given as transition table as below.
- Design a Mealy machine that uses its state to remember the last symbol read and emits output ‘y’ whenever current input matches to previous one, and emits n otherwise.
Ans: The example of Mealy machine is designed to generate the output as “y” if current input matches with the previous input and output “n” Consider the language formed with a’s and b’s on {a|b}*. For input abb the final output would be “y” and for input aba the output would be “n”. the mealy machine designed is as follows.
- Construct the Left Linear Grammar for the following Regular Expressions:
- (11 + 0)* (00 + 1)*
- 10 + (0 + 11)0*1
Ans: for the regular expression the left linear grammar is as follows.
- (11 + 0)* (00 + 1)*
Corresponding Left Linear grammar is
S→ A00 | A1 | ε,
A→ A00 | A1 | B,
B→ B11 | B0 | ε
- 10 + (0 + 11)0*1
Corresponding Left Linear grammar is
S→ 10 | A1
A→ B0 |C
B → 11 | 0
- Design DPDA for the language L = { a^{n} b^{2n} / n>0}
Ans: The strings accepted in this language are all a’s followed by b’s where the number of b’s is twice the number of a’s. PDA M = ({q_{0}, q_{1}, q_{2}}, {a, b}, {a, Z_{0}}, δ, q_{0}, Z_{0}, {q_{f}}), where δ is defined by following rules:
δ(q_{0}, a, Z_{0}) = {(q_{0}, aZ_{0})}δ(q_{0}, a, a) = {(q_{0}, aa)}δ(q_{0}, b, a) = {(q_{1}, a)}δ(q_{1}, b, a) = {(q_{2}, ε)}δ(q_{2}, b, a) = {(q_{1}, a)}δ(q_{2}, ε, Z_{0}) = {(q_{f}, Z_{0})}To show that aabbbb is accepted by the PDA ID’s of the system while processing the string are as follows.
(q_{0}, aabbbb, Z_{0}) ⇒ (q_{0}, abbbb, aZ_{0}) ⇒ (q_{0}, bbbb, aaZ_{0}) ⇒(q_{2}, bb, aZ_{0}) ⇒ (q_{1}, b, aZ_{0}) ε, Z_{0}) ⇒ (q_{f}, ε, Z_{0})
- Explain in brief the properties of recursive and recursively enumerable languages
Ans: There are three possible outcomes of executing a Turing machine over a given input. The Turing machine may
- Halt and accept the input;
- Halt and reject the input; or
- Never halt.
A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language. Note: If a language L is recursive, then its complement L must also be recursive.
A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.)
- Prove that PCP is undecidable
Ans: Given an alphabet S, one instance of Post’s correspondence problem of size s is a finite set of pairs of strings (g_{i}, h_{i}) (i = 1...s s> = 1) over the alphabet S. A solution of length n > = 1 to this instance is a sequence i_{1} i_{2} ... in of selections such that the strings gi1gi2 ... gin and h_{i}_{1}h_{i}_{2} ... hin formed by concatenation are identical.
Width of a PCP instance is the length of the longest string in g_{i} and h_{i} (i = 1, 2, ..., s). Pair i is the short name for pair (g_{i}, h_{i}), where gi and h_{i} are the top string and bottom string of the pair respectively. Mostly, people are interested in optimal solution, which has the shortest length over all possible solutions to an instance. The corresponding length is called optimal length. We use the word hard or difficult to describe instances whose optimal lengths are very large. For simplicity, we restrict the alphabet S to {0, 1}, and it is easy to transform other alphabets to their equivalent binary format.
To describe subclasses of Post’s Correspondence Problem, we use PCP[s] to represent the set of all PCP instances of size s, and PCP[s, w] the set of all PCP instances of size s and width w.
For convenience, we use a matrix of 2 rows and s columns to represent instances of PCP[s], where string gi is located at (i, 1) and h_{i} at (i, 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in
ig_{i}h_{i}11001201003100Let’s consider the result of selections of pair 1, 3, 1, 1, 3, 2, 2 accordingly. They can be shown in the following table with each selection assigned a different color. After the elimination of blanks and concatenation of strings in the top and bottom separately, it turns to:
10011001001001001100100100Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.
- Design Turing Machine over Σ_ = {1} to accept the language L = {1^{m} / m is odd}
- Write about:
a) Multi tape Turing Machine
b) NP Hard and NP Complete problem
Ans: (a) Multitape Turing machine
It is a kind of Turing machines that has one finite control and more than one tapes each with its own read-write head. It is denoted by a 7-tuple ((Q, Σ, γ, δ, q^{0}, B, F). Its transition function is a partial function
δ :QX(Г∪ {B})^{n} → (Q{h})X(Г∪{B})^{n}X{R,L,S}^{n}A configuration for this kind of Turing machine must show the current state the machine is in and the state of each tape. It can be proved that any language accepted by an n-tape Turing machine can be accepted by a one tape Turing machine and that any function computed by an n-tape Turing machine can be computed by a one tape Turing machine. Since the converses are obviously true, one can say that one tape Turing machines are as powerful as n-tape Turing machines.
(b) NP Hard and NP Complete Problems
The subject of computational complexity theory is focused on classifying problems by how hard they are. There are many different classifications depending the time taken by the problem. The following are the types of classification.
- P. Problems are those that can be solved by a Turing Machine (deterministic) in polynomial time. (“P” stands for polynomial). P problems are class of problems which can be solved efficiently.
- NP. Problems are those that can be solved by nondeterministic Turing machine in polynomial time. A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution). NP problems are class of problems which cannot be solved efficiently. NP does not stand for “non-polynomial”. There are many complexity classes that are much harder than NP.
- Undecidable. For some problems, we can prove that there is no algorithm that always solves them, no matter how much time or space is allowed. One very uninformative proof of this is based on the fact that there are as many problems as there real numbers, and only as many programs as there are integers, so there are not enough programs to solve all the problems. But we can also define explicit and useful problems which can’t be solved.
- Explain the steps in conversion of NFA to DEA convert the following NFA to DFA.
Ans:
Q = 2^{3} = 8 states = all subsets of q_{0}, q_{1}, q_{2}
= {∅, [q_{0}], [q_{1}], [q_{2}], [q_{0}, q_{1}], [q_{0}, q_{2}], [q_{1}, q_{2}], [q_{0}, q_{1}, q_{2}]}
Σ = 0, 1
q_{0 } = [q_{0}]
F = {[q_{2}], [q_{0}, q_{2}], [q_{1}, q_{2}], [q_{0}, q_{1}, q_{2}]}
δ is given by δ_{D} ([q_{1} q_{2}], a) = δ _{n} (q_{1}, a) U δ_{n} (q_{2}, a)
when δ_{n} is transition function NFA.
01∅∅∅→[q_{0}][q_{0}, q_{1}][q_{0}][q_{1}]∅[q_{2}][q_{2}]∅∅[q_{0,} q_{1}][q_{0, }q_{1}][q_{0}, q_{2}]*[q_{0,} q_{2}][q_{0,} q_{1}][q_{0}][q_{1}, q_{2}]∅[q_{2}][q_{0}, q_{1}, q_{2}][q_{0}, q_{1}][q_{0}, q_{2}]The states [∅], [q_{1}], [q_{2}], [q_{1}, q_{2}] and [q_{0}, q_{1}, q_{2}] are not reachable from start stated hence cannot define any strings. So they can be thrown away. Hence the DFA can be simplified as follows in Fig 2.28:
To get this Simplified DFA construct the states of DFA as follows
- Start with initial state. Do not add all subsets of states as there may be unnecessary states.
- After finding the transition on this initial state, include only the resultant states into the list until no new state is added to the list. For example if δ(q_{0}, a) = {q_{0}, q_{1}} say then add this as new state in DFA. and find transition from this state on input symbol.
- Declare the states as final if it has at least one final state of NFA.
- Prove that, if L is accepted by an NFA with Ø transactions, then L is accepted by NFA without Ø transactions
Ans: For each state compute ε-closure(q) on each input symbol a ∈ Σ. If the ε-closure of a state contains a final state then make the state as final.
Let the following be NFA with ε – transitions
The transition table is
Step 1: Find ε-closure of each state.
ε-closure (q_{0}) = {q_{0}, q_{1}, q_{2}}
ε-closure (q_{1}) = {q_{1}, q_{2}}
ε-closure (q_{2}) = {q_{2}}
Step 2: Find the transition on each state for each element.
(q_{0}, 0) = ε-closure (δ(ε-closure (q_{0}), 0))= ε-closure (δ({q_{0}, q_{1}, q_{2}}, 0))= ε-closure ({q_{0}}, ∪{Ø}, ∪{Ø})= {q_{0}, q_{1}, q_{2}}(q_{0}, 1) = ε-closure (δ(ε-closure (q_{0}), 1))= ε-closure (δ({q_{0}, q_{1}, q_{2}}, 1))= ε-closure ({Ø}, ∪{q_{1}}, ∪{Ø})= {q_{1}, q_{2}}(q_{0}, 2) = ε-closure (δ(ε-closure (q_{0}), 2))= ε-closure (δ({q_{0}, q_{1}, q_{2}}, 2))= ε-closure ({Ø}, ∪{Ø}, ∪{q_{2}})= {q_{2}}(q_{1}, 0) = ε-closure (δ(ε-closure (q_{1}), 0))= ε-closure (δ({q_{1}, q_{2}}, 0))= ε-closure ({Ø})= {Ø}(q_{1}, 1) = ε-closure (δ(ε-closure (q_{1}), 1))= ε-closure (δ({q_{1}, q_{2}}, 1))= ε-closure ({q_{1}}, ∪{Ø})= {q_{1}, q_{2}}(q_{1}, 2) = ε-closure (δ(ε-closure (q_{1}), 2))= ε-closure (δ({q_{1}, q_{2}}, 2))= ε-closure ({Ø}, ∪{q_{2}})= {q_{2}}= ε-closure (δ({q_{2}}, 0))= ε-closure ({Ø})= {Ø}(q_{2}, 1) = ε-closure (δ(ε-closure (q_{2}), 1))= ε-closure (δ({q_{2}}, 1))= ε-closure ({Ø})= {Ø}(q_{2}, 2) = ε-closure (δ(ε-closure (q_{2}), 2))= ε-closure (δ({q_{2}}, 2))= ε-closure ({q_{2}})= {q_{2}}NFA without – ε transitions is
Transition diagram of NFA without ε-transitions
- Prove the equivalence of NFA and DFA using subset construction.
Ans:Let M_{N} = (Q_{N}, Σ_{N}, δ_{n}, q_{ON}, F_{N}) be given NFA to construct equivalent DFA M_{D} define M_{D} as follows.
- Q_{D} = 2^{Q}_{N. }If NFA has n states. DFA at most can have 2^{n} states.
- Σ_{n} = Σ_{D}
- [q_{0}] = {q_{o}}
- F_{D} = Set of all states of Q_{D} that contains at least one final states of F_{N}.
- δ_{D }((q_{1}, q_{2}, q_{3}), a) = δ_{n}(q_{1}, a) ∪ δ_{n} (q_{2}, a) ∪ δ_{n}(q_{3}, a)
= {P_{1}, P_{2}, P_{3}} say
Add state [ P_{1}, P_{2}, P_{3}] to Q_{D} if it is not there.
- Give Deterministic finite automata accepting the following language over the alphapet.
- Number of 1’s is a multiples of 3
Ans: To construct DFA to satisfy the given conditions we need to have the number of 1’s as multiple of three.
- Number of 1’s is not a multiples of 3
- Number of 1’s is a multiples of 3
- Convert the following NFA into a regular expression.
Ans: the strings generated are the third symbol from the right end is 1. The regular expression is (1 + 0)*1(1 + 0)(1 + 0)
- Discuss the closure properties of regular languages.
Ans: The principal closure properties of regular languages are:
- The union of two regular languages is regular. If L and M are regular languages, then so is L ∪ M.
- The intersection of two regular languages is regular. If L and M are regular languages, then so is L ∩ M.
- The compliment of two regular languages is regular. If L is a regular language over alphabet Σ, then Σ*-L is also regular language.
- The difference of two regular languages is regular. If L and M are regular languages, then so is L − M.
- The reversal of a regular language is regular. The reversal of a string means that the string is written backward, i.e. reversal of abcde is edcba. The reversal of a language is the language consisting of reversal of all its strings, i.e. if L = {001, 110} then L(R) = {100, 011}.
- The closure of a regular language is regular. If L is a regular language, then so is L*.
- The concatenation of regular languages is regular.If L and M are regular languages, then so is L M.
- The homomorphism of a regular language is regular.A homomorphism is a substitution of strings for symbol. Let the function h be defined by h(0) = a and h(1) = b then h applied to 0011 is simply aabb. If h is a homomorphism on alphabet Σ and a string of symbols w = abcd…z then h (w) = h (a) h (b) h(c) h (d)…h (z) The mathematical definition for homomorphism is h: Σ*→Γ* such that ∀ x, y ∈ Σ* and h(x), h(y) ∈ τ*. A homomorphism can also be applied to a language by applying it to each of strings in the language. Let L be a language over alphabet Σ, and h is a homomorphism on Σ, then h (L) = {h(w) | w is in L} The theorem can be stated as “ If L is a regular language over alphabet Σ, and h is a homomorphism on Σ, then h(L) is also regular ”.
- The inverse homomorphism of two regular languages is regular. Suppose h be a homomorphism from some alphabet Σ to strings in another alphabet T and L be a language over T then h inverse of L, h′ (L) is set of strings w in Σ* such that h(w) is in L. The theorem states that “ If h is a homomorphism from alphabet Σ to alphabet T, and L is regular language on T, then h′(L) is also a regular language”.
- Discuss the application of regular languages.
Ans: The regular languages are useful in defining the tokens in a language which can be recognized during Lexical analyzers and by Text editors.
Lexical analyzers: The tokens of the programming language can be expressed using regular expressions. The lexical analyzer scans the input program and separates the tokens. For eg identifier can be expressed as a regular expression as: (letter)(letter + digit)* If anything in the source language matches with this reg exp then it is recognized as an identifier. The letter is{A, B, C, ………..Z, a, b, c….z} and digit is {0, 1, …9}. Thus reg exp identifies token in a language.
Text editors: These are programs used for processing the text. For example UNIX text editors uses the reg exp for substituting the strings such as: S/bbb*/b/
Gives the substitute a single blank for the first string of two or more blanks in a given line. In UNIX text editors any reg exp is converted to an NFA with ∈ –transitions, this NFA can be then simulated directly.
- Using pumping lemma for regular sets prove that the language
L = {0^{m}1^{n}0^{m-n} | m ≥ 1 and n ≥ 1} is not regular.
Let us assume that the language is regular. According to Pumping lemma choose the string Z = 0^{m }1^{n }0^{m} + ^{n} where the length is 2(m + n). Let n be the number of states such that | Z | ≥ n. Now let us represent the string Z as UVW and if the language is regular then for all i, UV^{i}W ∈ L.
To check whether it is regular or not, it is required to consider three possible cases i) where the string V is formed with only 0’s or ii) with only 1’s or iii) with the combination of 0’s and 1’s.
Case 1: V is a string such that it contains only 0’s.
V = 0^{x} Such that x ≥ 1.
Let i = = 0, then the string formed is UW, the string would be of the form 0^{m}^{-}^{x }1^{n }0^{m} + ^{n }∉L as the number of 0’s is less than the number of 1’s and 0’s after it.
Case 2: V is a string such that it contains only 1’s.
V = 1^{x} Such that x ≥ 1.
Let i = 0, then the string formed is UW, the string would be of the form 0^{m }1^{n}^{-}^{x }0^{m} + ^{n }∉L as the number of 1’s is less than the number of 0’s.
Case 3: V is a string such that it contains combination of 0’s and 1’s.
V = 0^{x}1^{x} Such that x ≥ 1.
If i = 0, then the string formed is UW, the string would be of the form 0^{m}^{-}^{x }1^{n}^{-}^{x }0^{m} + ^{n }∉L as the number of 0’s and number of 1’s is not equal to number of 0’s.
Since in all the three possible cases there exists value of i such that the string is not in L. Hence the language is not regular.
- Convert the following grammar into GNF.
S →XY1/0
X →00X/Y
Y→1X1
Ans: Step 1: Since there are unit productions first eliminate it and the resulting grammar is
S → XY1/0X → 00X/1X1Y → 1X1Step 2: Converting the grammar to CNF we get
S → XP/0P → YBX → AQ/BRQ → AXR → XBY → BRA→ 0B → 1Step 3: Converting the grammar to GNF we get
S → 0QP | 1RP |0P → 1RBX → 0Q/1RQ → 0XR → 0QB | 1RBY → 1RA → 0B → 1 - Give formal pushdown automata that accepts {wcw^{R} | w in (0 + 1)^{*}} by empty stack.
Ans: Read the string w and push it on to the stack till it encounters ‘c’. After that read each symbol, if it matches with top of the stack pop off the symbol. When input is read completely, then if it enters the final state, then it is successful.
The PDA can be given as follows:
Let q_{0} be initial state, q_{f} be final state and Z_{0 }be bottom of the stack.
δ(q_{0}, 0, Z_{0}) = (q_{0}, 0Z_{0})δ(q_{0}, 0, 0) = (q_{0}, 00)δ(q_{0}, 0, 1) = (q_{0}, 01)δ(q_{0}, 1, Z_{0}) = (q_{0}, 1Z_{0})δ(q_{0}, 1, 1) = (q_{0}, 11)δ(q_{0}, c, Z_{0}) = (q_{1}, Z_{0})δ(q_{0}, c, 0) = (q_{1}, 0)δ(q_{0}, c, 1) = (q_{1}, 1)δ(q_{1}, 0, 0) = (q_{1}, ε)δ(q_{1}, 1, 1) = (q_{1}, ε)δ(q_{1}, ε, Z_{0}) = (q_{f }, Z_{0})The final PDA is given by M = {(q_{0}, q_{1}, q_{f}), (a, b, c), (a, b, Z_{0}), δ, q_{0}, Z_{0}, {q_{f}}}.
- Show that the following grammars are ambiguous.
{S → aSbS / bSaS / ε} and
Ans: The string abab can be derived using LMD as follows
- S = > aSbS = >abS = > abaSbS = > ababS = > abab
- S = > aSbS = > abSaSbS = > abaSbS = > ababS = > abab
Since there are two possible ways to derive the string it is ambiguous for w
{S → AB / aaB, A → a/ Aa, B→b}
Ans: The string aab can be derived using LMD as follows
- S = > AB = >AaB = > aaB = > aab
- S = > aaB = > aab
Since there are two possible ways to derive the string it is ambiguous for w
(ii) Prove the equivalence of PDA and CFL.
Suppose L is a context-free language. Then there is a PDA M such that L = N(M).
Proof: The basic idea in the construction is to build M so that it simulates the leftmost derivation of strings using G. The machine we construct uses the terminals and non-terminals of the grammar as stack symbols. What we conceptually want to do is to use the stack to hold the sentential form that evolves during a derivation. At each step, the topmost variable in the stack will get replaced by the RHS of some grammar rule. Of course, there are several problems with implementing this concept. For one, the PDA can only access the top of its stack it can’t find a variable below the top. For another, even if the PDA could find such a variable, it could not fit the RHS into a single stack slot. But these are not insurmountable. We simply have to arrange things so that the PDA always has the leftmost variable of the sentential form on top of the stack. If that can be set up, the PDA can use the technique of using extra states to push multiple symbols ‘all at once’.
The other consideration is that we are constructing a PDA, so it needs to consume the input string and give a verdict. This fits in nicely with our other requirements. In brief, the PDA will use ε-transitions to push the RHS of rules into the stack, and will use ‘normal’ transitions to consume input. In consuming input, we will be able to remove non-variables from the top of the stack, always guaranteeing that a variable is at the top of the stack.
We assume that ε is not in L(G) and let G be given as (V, T, P, S) be a context free grammar in Greibach normal form. It is required to construct M = ({q}, T, V, δ, S, ɸ) where δ(q, a.A) contains (q, γ) whenever A→aγ is in P.
The PDA M simulates leftmost derivations of G. Since G is in Griebach normal form, each sentential form in a leftmost derivation consists of terminals x followed by a string of variables α. M stores the suffix α of the left sentential form on its stack after processing the prefix x. Formally we show that
S⇒xα by a leftmost derivation if and only if (q, x, S) (q, ε, α)
- Explain Turing machine as a computer of integer functions with an example.
Ans: A TM M computes a function f if, when given input w in the domain of f, the machine halts in its accept state with f(w) written (leftmost) on the tape. To use Turing Machine as a computational machine it is required to place the integer numbers as 0^{m}. Suppose it is required to add two numbers, ie. f(m, n) = m + n then the numbers m and n are to be placed on the tape as 0^{ m}10^{ n} where 1 is separator for the numbers m and n. Once processing is completed and the turing machine halts then the tape would have the contents as 0^{ (m} + ^{n)} which is the required result of computation.
Example: The addition of these numbers using simple logic is explained as below. The numbers are placed as B0^{2}10^{3}B. After processing the tape content would be B0^{5}B. The simple logic that can be used is replace the occurrence of 1 by 0 and move to right end and replaces the last 0 to B so that it is in required form as B0^{5}B. Sequence of steps is given for understanding.
- In initial state 0’s is replaced by B and change to new state.
δ(q0, 0) = (q1, B, R)
- If this state travel right until it encounters 1. replace this 1 by 0 be in the same state and on seeing B halt.
δ(q1, 0) = (q1, 0, R)
δ(q1, 1) = (q1, 0, R)
δ(q1, B) = (qA, B, R)
B•001000B├B•01000B├ B0•1000B├B00•000B├ B000•00B├ B0000•0B├ B00000•B├ B00000B
- In initial state 0’s is replaced by B and change to new state.
- Write the procedure to remove ∈ productions from the given grammar.
Ans: If some CFL contains the word ε, then the CFG must have a ε-production. However, if a CFG has a ε-production, then the CFL does not necessarily contain ε. e.g.
S → aX
X → ε
which defines the CFL {a}.
Nullable variable: In a given CFG, a nonterminal X is nullable if
- There is a production X → ε
- There is a derivation that starts at X and leads to ε:
X = > . . . = >ε i.e., Xε
For any language L, define the language L_{0} as follows:
- if ε ∉L, then L_{0} is the entire language L, i.e., L_{0} = L.
- if ε ∈ L, then L_{0} is the language L - {ε}, so L_{0} is all words in L except ε.
⇒Note: If L is a CFL generated by a CFG G1 that includes ε-productions, then there is another CFG G2 with no ε-productions that generates L_{0}.
Procedure for eliminating ε productions:
- Construct V_{n} set of all nullable variables
- For each production B → A, if A is nullable variable, replace nullable variable by ε and add with all possible combinations on the RHS.
- Do not add the production A → ε
- Write short notes on the following:
- Two-way infinitentape TM.
Ans: In all our formulations we specified that the tape had an left end and stretched infinitely far to the right. Relaxing this stipulation to allow the tape to stretch infinitely far too right and left results in a new formulation of Turing machines equivalent to the original. That is for any Turing machine using a two way tape there is a Turing machine with a one-way infinite tape with the same input-output behavior, and vice versa.
One can simulate a Turing machine with two way infinite tape on a Turing machine with one way infinite tape. Let the two way infinite tape have the contents as shown below.
Let the reading head be left of A_{0}. This can be simulated by a Turing machine with one way infinite tape with two tracks having the contents placed such that the contents of the tape right of A_{0} are placed on the upper track and the contents of the tape to the left of A_{0 }are placed on the lower track in reverse order. The left end cell contains on upper track and a special symbol Φ on the lower track as shown below.
The moves are simulated such that when the reading head is to the right of A_{0} the moves are implemented as they are reading symbols from upper track. If the reading head is to the left of A_{0} then symbols are read from lower head but the direction of reading head would be in opposite direction to the direction in which it moves on two way infinite tapes. That is if it moves left then on one way infinite tape it moves right or vice versa.
Many other variations of Turing machine are possible. However, it has been shown that none of them exceed the capability of basic deterministic Turing machine as far as accepting languages is concerned. In fact the Church’s thesis conjectures that any so called computation done by humans or computers can be performed by a basic deterministic Turing machine.
- Multiple tracks TM.
Ans: The tape is imagined as divided into cells where input to be processed is placed. We can further imagine that the tape is divided into k tracks for some finite number k as shown below.
The reading head considers k symbols each belonging to different track in same column and processes it. There are two special symbols ɸ and $ used in the first track which indicates the boundary of the input. The other tracks are used to place the intermediate results and the final result of the processing. The blank input is identified as the all B’s in all tracks as [B, B, B]. The input at the current position of the reading head is [1, 1, 1].
Example: To design a TM to identify the number as prime or not it is required to find whether the number has factors other than itself.
- Let us place the given number on first track in binary form bounded by Φ and $. For example 47 is represented as Φ101111$.
- On the second track write 2 in binary form as 10.W
- Copy the number on first track to third track.
- Perform repeated subtraction of number on third track with number on second track until the number on third track is either 0 or less than number on second track.
- If the number on third track is zero and number on second is not equal to number on first track then the number on first track is not prime, otherwise not prime.
- If the number on third track in nonzero and increase number on second track by one.
- Repeat the steps 4-6 until the number on second is equal to number on first.
- Two-way infinitentape TM.
- Write the classes and definition of NP problems.
Ans: The subject of computational complexity theory is focused on classifying problems by how hard they are. There are many different classifications depending the time taken by the problem. The following are the types of classification.
- P. Problems are those that can be solved by a Turing Machine (deterministic) in polynomial time. (“P” stands for polynomial). P problems are class of problems which can be solved efficiently.
- NP. Problems are those that can be solved by nondeterministic Turing machine in polynomial time. A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution). NP problems are class of problems which cannot be solved efficiently.NP does not stand for “non-polynomial”. There are many complexity classes that are much harder than NP.
- Undecidable. For some problems, we can prove that there is no algorithm that always solves them, no matter how much time or space is allowed. One very uninformative proof of this is based on the fact that there are as many problems as there real numbers, and only as many programs as there are integers, so there are not enough programs to solve all the problems. But we can also define explicit and useful problems which can’t be solved.
- Prove that if a language is recursive if and only if it and its complement are both recursively enumerable.
Ans: A language L is recursively enumerable if there is a TM that accepts L and recursive if there is a TM that recognizes L. Thus r.e language is Turing acceptable and recursive language is Turing decidable languages. No, the language accepted by non-deterministic Turing machine is same as recursively enumerable language.
Recursive languagesRecursively enumerable languages1. A language is said to be recursive if and only if there exists a membership algorithm for it.
2. A language L is recursive iff there I (Turing decidable languages). TMs that decide languages are algorithms. s a TM that decides L.
1. A language is said to be r.e if there exists a TM that accepts it.
2. L is recursively enumerable iff there is a TM that semi-decides L. (Turing acceptable languages). TMs that semi-decides languages are not algorithms.
(ii) Example about undecidability of PCP.
Given an alphabet S, one instance of Post’s correspondence problem of size s is a finite set of pairs of strings (g_{i}, h_{i}) (i = 1...s s> = 1) over the alphabet S. A solution of length n > = 1 to this instance is a sequence i_{1} i_{2} ... i_{n} of selections such that the strings g_{i1}g_{i2} ... g_{in} and h_{i1}h_{i2} ... h_{in} formed by concatenation are identical.
Width of a PCP instance is the length of the longest string in g_{i} and h_{i} (i = 1, 2, ..., s). Pair i is the short name for pair (g_{i}, h_{i}), where g_{i} and h_{i} are the top string and bottom string of the pair respectively. Mostly, people are interested in optimal solution, which has the shortest length over all possible solutions to an instance. The corresponding length is called optimal length. We use the word hard or difficult to describe instances whose optimal lengths are very large. For simplicity, we restrict the alphabet S to {0, 1}, and it is easy to transform other alphabets to their equivalent binary format.
To describe subclasses of Post’s Correspondence Problem, we use PCP[s] to represent the set of all PCP instances of size s, and PCP[s, w] the set of all PCP instances of size s and wisdth w.
For convenience, we use a matrix of 2 rows and s columns to represent instances of PCP[s], where string gi is located at (i, 1) and hi at (i, 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in PCP[3, 3].
ig_{i}h_{i}11001201003100Let’s consider the result of selections of pair 1, 3, 1, 1, 3, 2, 2 accordingly. They can be shown in the following table with each selection assigned a different color:
After the elimination of blanks and concatenation of strings in the top and bottom separately, it turns to:
10011001001001001100100100Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.
- Describe the fundamental differences in the rules for forming DFA and NFA. Are these differences important in terms of the languages they can recognize? Give a reason for your answer. (8)
Ans: Properties of Transition Function (δ)
- δ (q, ε) = q
This means the state of the system can be changed only by an input symbol else remains in original state.
- For all strings w and input symbol a
δ(q, aw) = δ(δ(q, a), w)
similarly δ(q, wa) = δ(δ(q, w), a)
- The transition function δ can be extended to
(or) that operates on states and strings (as opposed to states and symbols)
Basis: (q, ε) = q
Induction: (q,xa) = δ((q, x ),a)
Language of a DFA
A string x is said to be accepted by DFAM = (Q, Σ, S, F, δ), if δ(q_{0}, x) = P for some P in F.
Method: A finite automata accepts a string w = a_{1} a_{2} … a_{n} if there is a path in the transition diagram which begins at a start state ends at an accepting state with the sequence of labels a_{1} a_{2} … a_{n}
- The Language accepted by finite automata (A) is
L(A)={w :(q_{0},w) ∈F} where F is a final state.
- The language accepted by finite automata’s are called “regular language”
Extended Transition Function ( )
Basis: (q, ε)={q}
Induction:
(q,wa)= δ(P,a) for each w ∈Σ*,a ∈Σand P∈(q,w)
Language of a NFA
Language accepted by NFA is L(A) = {w :( q_{0} ,w)∩F≠ɸ}
Transition function and language of ε–NFA
The transition function is defined as:
- (q, ε) = ε – CLOSURE(q)
- For w in Σ*, and a in Σ
(q, wa) = ε-CLOSURE(P)
Where P = {p │ for some r in (q,w), p in δ(r,a)}
- (R,a)=δ(q,a)
- (R,w)=(q,w)
The language accepted by NFA with ε – move is defined as:
L (M)={w | (q,w) contains a state in F}
In each model the transition rules are defined as per the model, but the language acceptance will be same for all the models.
- δ (q, ε) = q
- Construct an NFA for the following regular expression: (a + b)* a + b (8)
Ans: ⇒ (a + b)*
⇒ (a + b)*.a
⇒ (a + b)*.a + b
NFA (simplified)
- Consider the alphabet A = {a, b} and the language L = {bb, bab, baab, baaab,……} over A.
- Is A* finite or infinite? Give a brief reason for your answer. (2)
- Write down a regular expression that represents the above language L. (4)
- Write down a regular grammar which describes the above language L. (4)
- Draw the DFA corresponding to the above language L. (6)
Ans: Given:
A = {a, b}
L = {bb, bab, baab, baaab, …..}
Solution:
- Find an equalities for the following regular expression and prove for the same.
- b + ab* + aa*b + aa*ab*
- a*(b + ab*)
- a(a + b)* + aa(a + b)* + aaa(a + b)* (9)
- Ans: (1) b + ab* + aa*b + aa*ab*
= (b + ab*) + aa*(b + ab*)
= (ε + aa*) (b + ab*)
- a*(b + ab*)
= a*b + a*ab* = a* b + a + b*
- a (a + b)* + aa (a + b)* + aaa(a + b)*
= (a + aa + aaa) (a + b)*
- State and prove using an example, the properties of regular language. (7)
Ans: If a class of languages is closed under a particular operation we call that fact a closure property of the class of languages.
In this section we discuss the closure properties of regular sets under (a) union (b) concatenation (c) closure (d) complementation (e) intersection (f ) transpose (g) substitution (h) homomorphism.
Theorem
The regular sets are closed under union, concatenation and closure.
Proof
Let L_{1} and L_{2} be regular sets such that
L_{1} = T(A_{1}) and L_{2} = T(A_{2}) where
A_{1} = (Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ) and A_{2} = (Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2})
We shall assume that Q_{1} ∩ Q_{2} = ɸ
- Union: Let A = (Q, Σ, δ, q_{0}, F), where
Q = Q_{1} ∪ Q_{2} ∪ {q_{0} }, q_{0} E Q_{1} ∪ Q_{2}
q_{0} is the start date, Σ = Σ_{1} ∪ Σ_{2}, F = F_{1} ∪ F_{2} and δ· is defined as follows:
δ(q_{0}, λ) = {q_{1}, q_{2}}
If q ∈ δ_{1}(p, a) then q ∈ δ(p, a)
If q ∈ δ_{2} (p, a) then q ∈ δ(p, a)
It is clear that T(A) = (L_{1 }∪ L_{2})
- Concatenation: Let A = (Q, Σ, δ, q_{0}, F ) where
Q = Q_{1} ∪ Q_{2}, Σ = Σ_{1} ∪ S_{2}, q_{0} = q_{1}, F = F_{2} and
δ is defined as follows:
δ (q, a) = {δ_{1}(q, a)} for each q in Q_{1} − F_{1}
δ (q, a) = {δ_{2}(q, a)} for each q in F_{1 }
and δ (q, a) = {δ_{2}(q, a)} for each q in Q_{1}
A word w is in L_{1}, L_{2} if w = w_{1 }w_{2} where w_{1} ∈ L_{1}and w_{2 }∈ L_{2}. This is equivalent to δ_{1}(q_{1}, w) being in F_{1} which is equivalent to w_{1} w_{2} being in T(A). Thus L_{1} L_{2} = T(A).
- Closure: Let L = T(A)be a regular set where
A = (Q, Σ, δ, q_{0}, F)
Let B = (Q, Σ, δ′, q_{0}, F),
Where δ′ is defined as follows:
δ′ (q, a) = {δ(q, a)} if q is in Q − F and
δ′ (q, a) = {δ(q, a), δ(q_{0}, a )} if q is in F
It is easy to see that L* = T(B). If λ is in L, then it is accepted by B. Otherwise, we can modify B to accept λ.
- Theorem
The class of regular sets is closed under complementation. That is if X is a regular set and X ⊆ Σ* −L is a regular set.
Proof
Let X be X(M) for DFA M = (Q, Σ_{1}, δ, q_{0}, F) and let X ⊆*. First we assume Σ_{1} = Σ, if there are symbols in Σ_{1} not in Σ, we may delete all transitions of M on symbols not in Σ·. The fact that X ⊆ Σ·* assures us that we shall not thereby change the language of M. If there are symbols in Σ not in Σ_{1}, then none of these symbols appear in words of X. we may therefore introduce a dead state d into M with δ(d, a) = d for all a in Σ and δ(q, a) = d for all q in Q and a in Σ − Σ_{1}. Now to accept Σ* − X, complement the final states of M. That is let M ′ = (Q, Σ, δ, q_{0}, Q − F).
The M′accepts a word w if and only if δ(q_{0}, w) is in Q − F, that is, w is in Σ*−X. Note that it is essential to the proof that M is deterministic and without y moves.
- Theorem
If X and Y are regular sets over Σ, then X ∩ Y is also regular.
Proof
X ∩ Y = X ∩ Y by Demorgan’s Law where–denotes complementation with respect to an alphabet including the alphabets of X and Y. Closure under intersection then follows from closure under union and complementation.
- Therorem
If L is regular then L^{R} is also regular.
As L is regular, we can construct aFA
M = (Q, Σ_{1}, δ, q_{0}, F ) such that T(M) = L.
We can construct a transition system (or transition diagram or transition graph) by M′ by starting with the state diagram of M, and reversing the direction of the directed edges. The set of initial states of M′ is defined as the set F, and q_{0 }defined as the (only)
final state of M′ (i.e.) M′ = (Q, Σ_{1}, δ, F, {q_{0}}).
If w ∈ T(M), we have a path from q_{0}, to some final state in F with value w. By reversing the edegs we get a pair in M from some final state in F to q_{0}. Its path value is w^{R}. So w^{R} ∈ T(M). In a similar way, we can see that if w_{1} ∈ T(M’), then w_{1}^{R} ∈ T(M). Thus from the state diagram it is easy to see that T(M′) = T(M)^{R}. We can prove that w ∈ T(M′) if w^{R} ∈ T(M′) by induction on │w│. Since T(M′) is regular it follows that T(M)^{R} is regular.
- Theorem
The class or regular sets is closed under substitution.
Proof
Let R ⊆ Σ* be a regular set and each for each a in Σ let Ra ⊆ Δ * be a regular set. Let f: Σ → Δ * be the substitution defined by f(a) = Ra. Select regular expressions denoting R and each Ra. Replace each occurrence of the symbol a in the regular expression for R by the regular expression denotes f(R), observe that the substitution of a union, product, or closure of the substitution.
A simple induction on the number of operators in the regular expression completes the proof.
- Theorem
The class of regular sets is closed under homomorphisms and inverse homomorphisms.
Proof
Closure under homomorphisms follows immediately from closure under substitution, since every homomorphism is a substitution in which h(a) has one member.
To show closure under inverse homomorphism, let M = (Q, Σ, δ, q_{0}, F) be a DFA accepting L, and let h be a homomorphism from Δ to Σ*. We construct a DFA M′ that accepts h(L) by reading symbol a in Δ and simulating M on h(a). Formally let M′ = (Q,Δ, δ′, q_{0}, F) and define δ′(q, a) for q in Q and a in Δ to be δ (q, h (a)). Note that h(a) may be a long string or λ but δ is defined on all strings by extension. It is easy to show by induction on │x│ that δ′(q_{0}, x) = δ(q_{0}, h(x)). Therefore M′ accepts x if and only if M accepts h(x). That is L(M′) = h^{-}^{1}L(M).
- Union: Let A = (Q, Σ, δ, q_{0}, F), where
- State the algorithm for minimization of a DFA. Construct a minimized DFA for the regular expression (a + b)(a + b)* and trace for the string baaaab. (16)
Ans: His minimization algorithm finds a DFA M’ equivalent to the DFA M′ = (Q, Σ,δ, q_{0}, F) with reduced number of states.
Steps
- Mark the pair of inequivalent states (p, q) with ‘X’
- Initially ‘X’ is placed by considering one final state and one non-final state, where δ(p, x) ∈ F and δ(q, x) ∈ F.
- If δ(p, a) = r and δ(q, a) = s for input symbol a and the states r, s are already distinguishable by some string x, then p, q are distinguished by ax, otherwise (p, q) is placed in a list associated with (r, s) entry.
- From the unmarked states, each pair of equivalent states are identified.
- New states of DFA has pair of equivalent states and the states which are not in the equivalent pairs are individual states.
- Construct DFA transition table with reduced number of states.
Algorithm for marking pairs of inequivalent states
Begin
for p in F and q in Q−F do mark (p, q):
for each pair of distinct states(p, q) in F x F or (Q − F) x (Q − F) do
if for some input symbol a, ( δ(p, a), δ(q, a)) is marked then
begin
mark (p, q);
Recursively mark all unmarked pairs on the list for (p, q) and on the lists of other pairs that are marked at this step.
end
else/* no pair (δ(p, a), δ(q, a)) is marked*/
for all input symbols a do
put(p, q) on the list for (δ(p, a), δ(q, a)) unless
δ(p, a) = δ(q, a)
end
εNFA for RE = (a + b)(a + b)*
In this simplification NFA is equivalent to DFA, since every state, transition is defined for all symbols.
Transition table of DFA:
StatesInputsab→q_{0}
q_{0}q_{0}*q_{1}
q_{1}q_{1}In this representation q_{0} is the start date and q_{1} is the final state. Therefore it can’t be reduced further.
Given w = baaab
δ(q_{0}, baaab)
= δ(δ(q_{0}, b), aaab)
= δ(q_{1}, aaab)
= δ(δ(q_{1}, a), aab)
= δ(q_{1}, aab)
= δ(δ(q_{1}, a), ab)
= δ(q_{1}, ab)
= δ(δ(q_{1}, a), b)
= δ(q_{1}, b)
= q_{1} ∈ F
String is accepted
- Mark the pair of inequivalent states (p, q) with ‘X’
- Consider the grammar:
- S → I C t S
- S → I C t S e S
- S → a
- C → b
where I, t, and, e stand for if, then, and else, and C and S for “conditional” and “statement” respectively.
- Construct a leftmost derivation for the sentence w = i b t i b t a e a.
- Show the corresponding parse tree for the above sentence.
- Is the above grammar ambiguous? If so, prove it.
- Remove ambiguity if any and prove that both the grammar produces the same language. (16)
Ans:
- w = i b t i b t a e a
Leftmost derivation 1:
S ⇒ i C t S
⇒ i b t S (C→b)
⇒i b t i C t SeS (S→i C t SeS)
⇒ i b t i bt SeS (C→b)
⇒ i b t i bt aeS (S→a)
⇒ i b t i bt aea (S→a)
- Leftmost derivation 2:
S ⇒ i C t S e S
⇒ i b t S E S (C→b)
⇒ i b t i C t S e S (S→iCtS)
⇒ i b t i b t S e S (C→b)
⇒ i b t i b t a e S (S→a)
⇒ i b t i b t a e a (S→a)
For the string w = i b t i b t a e a, the given grammar has two leftmost derivations. Therefore it is ambiguous.
- Consider the GNF CFG G = ({S, T, C, D}, {a, b, c, d}, S, P) where P is:
S→ cCD│dTC│∈ C→a T D │cT→ cDC│cST│a D→d C │ d
Present a pushdown automaton that accepts the language generated by this grammar.
Your PDA must accept by empty store, it must start with S on its stack, and it must be based on the above grammar. (16)
Ans: PDA is defined as M = (Q, Σ, Γ, δ, q_{0}, z_{0},ɸ )
where:
Q = {q_{0}, q_{1}, q_{2}}
Σ = {a, b, c, d}
Γ = {S, T, C, D, z_{0}}
δ is defined as:
δ(q_{0}, λ, z_{0}) = {(q_{1}, Sz_{0})}
δ(q_{1}, λ, S) = {(q_{1}, cCD), (q_{1}, dTC), (q_{1}, ε)}
δ(q_{1}, λ, T) = {(q_{1}, cCD), (q_{1}, cST), (q_{1}, a)}
δ(q_{1}, λ, C) = {(q_{1}, aTD), (q_{1}, c)}
δ(q_{1}, λ, D) = {(q_{1}, dC) (q_{1}, d)}
δ(q_{1}, a, a) = {(q_{1}, λ)}
δ(q_{1}, b, b) = {(q_{1}, λ)}
δ(q_{1}, c, c) = {(q_{1}, λ)}
δ(q_{1}, λ, z_{0}) = {(q_{2}, λ)}
- Define Pumping Lemma for Context Free Languages. Show that L =
{a^{i} b^{j} c^{k}: i < j < k} is not context-free. (6)
Ans: Let n be the pumping –lemma constant and consider string z = a^{n}b^{(}^{n} + ^{1)}c^{(}^{n} + ^{2)}
Write z = uvwxy, where v and x, may be “pumped”, and a│vwx│≤ n.
If vwx does not have c’s, then uv^{3}wx^{3}y has at least n + 2 a’s or b’s, and thus could not be in the language.
If vwx has a c, then it could not have an a, because its length is limited to n.
Thus, uwy has n a’s, but no more than 2n + 2 b’s and c’s in total.
Thus, it is not possible that uwy has more b’s than a’s and also has more c’s than b’s.
We conclude that uwy is not in the language, and now have a contradiction no matter how z is broken into uvwxy.
- Construct a Turing Machine^{TM} to move an input string over the alphabet A = {a} to the right one cell. Assume that the tape head starts somewhere on a blank cell to the left of the input string. All other cells are blank, labeled by ^. The machine must move the entire string to the right one cell, leaving all remaining cells blank. (10)
Ans: Given: A = {a}
Solution:
The format of the string in the tape is:
The required transition rules are:
δ(q_{0}, λ) = (q_{1}, λ, R)
δ(q_{1}, a) = (q_{2}, λ, R)
δ(q_{2}, a) = (q_{2}, a, R)
δ(q_{2}, λ) = (q_{3}, a, R) where q_{3} ∈ F
- Convert the following grammar into an equivalent one with no unit productions and no useless symbols. Convert to Chomsky Normal Form (CNF). (16)
S → A│CB
A → C│D
B → 1B│1
C → 0C│0
D → 2D│2
Ans: Given
S→A│CB
A→C│D
B→1B│1
C→0C│0
D→2D│2
Solution:
- No null productions, the unit productions are exist in the form of chain productions.
S → A
A → C
C → 0C│0 can be rewritten as
S → 0C│0
Similarly
S → A
A → D
D → 2D│2 can be rewritten as
S → 2D│2
The new set of productions are:
S → 0C│2D│CB│0│2
B → 1B│1
D → 2D│2
- Let G_{1} = (N_{1}, {0, 1, 2}, S, P_{1}) where P_{1} is:
S → 0│2│CB
B → 1 C → 0 D → 2 are added to P_{1}
S → 0C│2D, B → 1B C → 0C
D → 2D yield
S → A_{1}C│A_{3}D, B → A_{2}B, C → A_{1}C
D → A_{3}D, WHERE A_{1} → 0, A_{2} → 1, A_{2} → 2
∴ N_{1} = {S_{1} A_{1}, A_{2}, A_{3}, B, C, D}
Here G_{1} is in CNF for the given grammar
- No null productions, the unit productions are exist in the form of chain productions.
- Consider the language of all TMs that given no input eventually write a non-blank symbol on their tapes. Explain why this set is decidable. Why does this not conflict with the halting problem? (8)
Ans: Consider the language of all TMs that given no input eventually write a non-blank symbol on their tape. Since the controller is finite, there are only a finite number of states possible before the TM is forced to either loop or write a symbol, so we simply run the Turing machine for that number of steps and then accept if it has written a symbol and reject otherwise.
This does not conflict with the halting problem because we are considering only a subset of Turing machines (those roughly equivalent to DFAs) and not really addressing the halting problem for Turing machines.
- Prove that the Post Correspondence Problem is decidable for strings over the alphabet (0). (8)
Ans: We can simplify this problem by assigning each domino a value which is the number of 0s on the top row minus the number of zeros on the bottom row. Our goal, then, is to choose dominos whose values sum to zero. We consider a few cases:
- If the set contains a “0” domino, that domino alone is a legal solution, so we accept.
- If the set contains a “ + m” and “−n” domino, we construct a solution from n” + m”s and m “ + n”s and accept.
- If the set contains only “ + ” dominos or “–” dominos we cannot add them to zero, so we reject.
Since we can accept or reject based on a quick examination of the set of dominos, the problem is decidable.
- Prove that the problem of determining if the languages generated by two CFGs are equal is undecidable. (8)
Ans: We show this by reducing the problem of determining whether a CFG accepts everything to the problem of determining if the languages generated by tow CFGs are equal by taking our input CFG and comparing it to the CFG that generates everything. Since we know from class that the “everything” problem is undecidable, the “equal” probably must also be.
- Prove that the Punchcard Puzzle is NP-complete. (8)
Ans: We m of the formula. Then, we punch holes in the left column of the card in every position show that the problem is in NP by showing that it is verifiable in polynomial time. To do this, we simply stack the cards according to the answer presented in the certificate to determine if they cover all the holes. This can be accomplished easily in polynomial time.
To show that it is NP-complete, we reduce 3–SAT to it. We create cards {x_{1}, x_{2}, …} for each variable in the 3–SAT formula and create a hole position in each column fo reach terwhich corresponds to a term that does not contain that card’s variable and in the right column for every term which does not contain that card’s variable’s complement. The Punchcard problem is only satisfiable if every hole can be covered by one of the card which implies that every term in 3–SAT problem is satisfiable.
- Prove that for any language L recognized by an NFA with ε-transitions, there exists an NFA without ε-transitions to recognize L. (8)
Ans: Theorem
If L is accepted by NFA with ε-transitions, than L is accepted by an NFA without ε-transitions.
Proof
Let M = (Q, Σ, δ, q_{0}, F^{1}) be an NFA with ε-transitions. Construct M^{1} which is NFA without ε-transitions.
M^{1} =(Q, S, δ^{1}, q_{0}, F ) whereF1=F {q_{0} } if ε-CLOSURE (q_{0} ) contain a state of F.Let x be any string
δ^{1}(q_{0} , x)=δ(q_{0} ,x)
This statement is not ture if x = ε because δ^{1}( q_{0},ε )={q_{0}} and
(q_{0},ε) = ε-CLOSURE(q_{0})
Basic step
| x | = 1 x is a symbol whose value is
δ^{1}(q_{0},a)=δ(q_{0},a) (because by definition of )
Induction step
let x =wa where a is in Σ
δ^{1}(q_{0},wa )=δ^{1} (δ^{1} (q_{0} ,w ),a )
=δ^{1}(δ(q_{0},w),a)
= (p,a)[because by induction hypothesis
δ(q_{0},w)= (q_{0},w)=p(say)]
Now we must show that
δ^{1}(p,a)=δ(q_{0},wa)
But
δ^{1}(p,a)=δ^{1}(q,a)=δ(q,a)= δ(δ^{1}(q_{0},w),a)= δ(q_{0},wa)= (q_{0},x)Hence δ^{1}(q_{0},x) = (q_{0},x) - Construct an NFA without ε - transitions for the following NFS. (8)
Ans: NFA with ε-transition table (M):
NFA without ε-transition table (M^{1}):
The set of final states of M1=F∪{q_{0}}={q_{0},q_{2}}since ε-CLOSURE{q_{0}}={q_{0},q_{1},q_{2}}
Transaction diagram:
- For a given regular expression r, prove that there exists an NFA with transitions that accepts L(r). (8)
Ans: Theorem (Conversion of R.E. to FSA)
For every regular expression r there exists a NFA with ε−transitions that accepts L(r).
Proof
We prove by induction on the number of operators in the regular expression r that there is an NFA M with ε−transistors, having one final state and no transitions out of this final state such that L(M) = L(r).
Basis step (Zero operators)
Suppose r is ε, ɸ or a for some a∈∑. Then the equivalent NFA’s are:
- r = ε
- r = ɸ
- r = a
Induction (One or more operators)
Assume the theorem is true for r having fewer that i operators, i ≥1. Let r have i operators. We discuss three cases depending on the form of r.
Case 1:
Let r = r_{1} + r_{2}. Both r_{1} and r_{2} must have fewer that i operators. Thus there are NFA’s M_{1 } = (Q_{1}, ∑_{1}, δ_{1}, q_{1}, { f_{1}}) and M_{2 } = (Q_{2}, ∑_{2}, δ_{2}, q_{2}, { f_{2}}) with L(M_{1}) = L(r_{1}) and L(M_{2}) = L(r_{2}). Assume Q_{1} and Q_{2} are disjoint.
Let q_{0}, f_{0} be a new initial and final state respectively.
∴ M = (Q_{1}∪ Q_{2}∪ {q_{0}, f_{1}}, ∑_{1}∪∑_{2}, δ, q_{0}, { f_{0}}) where δ is defined by
- δ(q_{0}, ε) = {q_{1}, q_{2}}
- δ(q, a) = δ_{1} (q, a) if q∈Q_{1}−{ f_{1}}, a∈∑_{1}∪{ε}
- δ(q, a) = δ_{2} (q, a) if q∈Q_{2}−{ f_{2}}, a∈∑_{2}∪{ε}
- δ_{1}( f_{1}, ε) = δ_{2} ( f_{2}, ε) = { f_{0}}
All the moves of M_{1} and M_{2} are present in M. Any path in the transition diagram of M from q_{0} to f_{0} must being by going to either q_{1} or q_{2} on ε. If the path goes to q_{1}, it may follow any path in M_{1} to f_{1} and then goto f_{0} on ε.
Similarly paths that begin by going to q_{2}, may follow any path in M_{2} to f_{2} and then go to f_{0} on ε. These are the only paths from q_{0} to f_{0}. That is, there is a path labeled x in M_{1} from q_{1} to f_{1} or a path in M_{2} from q_{2} to f_{2}. Hence L(M) = L(M_{1}) ∪ L(M_{2})
Let r = r_{1} r_{2}. Let M_{1} and M_{2} be as in case 1. Construct M = (Q_{1} ∪ Q_{2}, ∑_{1} ∪ ∑_{2}, δ, {q_{1}}, { f_{2}}), where δ is given by
- δ(q, a) = δ_{1}(q, a) for q in Q_{1}−{ f_{1}} and a in ∑_{1} ∪ {ε}
- δ( f_{1}, ε) = {q_{2}}
- δ(q, a) = δ_{2}(q, a) for q in Q_{2} a in ∑_{2}∪{ε}
Every path in M from q_{1} to f_{2} is a path labeled by some string x from q_{1} to f_{1}, followed by the edge from f_{1} to q_{2} labeled ε, followed by a path labeled by some string y from q_{2} to f_{2}.
Thus L(M) = {xy|x is in L(M_{1}) and y is in L(M_{2})} and L(M) = L(M_{1}).L(M_{2}).
Case 3:
Let r = r_{1}^{*}. Let M_{1 } = (Q_{1}, ∑_{1}, δ_{1}, q_{1}, { f_{1}}) and L(M_{1}) = r_{1}. Construct M = (Q_{1}∪ {q_{0}, f_{0}}, ∑_{1}, δ, q_{0}, { f_{0}}), where δ is given by
δ(q_{0}, ε) = δ( f_{1}, ε) = {q_{1}, f_{0}}
δ(q, a) = δ_{1}(q, a) for q in Q_{1}−{ f_{1}} and a in ∑_{1}∪{ε}
Any path from q_{0} to f_{0} consists either of a path from q_{0} to f_{0} on ε or a path from q_{0}, to q_{1} on ε followed by some number of paths from q_{1} to f_{1}, then back to q_{1} on ε. There is a path in M from q_{0} to f_{0} labeled x if and only if we write x = x_{1}x_{2}……x_{j} fro some j ≥ 0 such that each x_{i}∈L(M_{1}). Hence L(M) = L(M_{1})^{*}
- Find the regular expression corresponding to the following automata. (8)
Ans: We will find R_{ij}^{(0)} where K = 0
R_{11}^{(0) } = ε
because from state q_{1} to q_{1} can be achieved only by ε transition.
R_{12}^{(0)} = 0
because from q1 we can reach q2 by ‘0’ input.
R_{13}^{(0)} = 1
because from q_{1} we can reach q_{3} by ‘1’ input δ(q_{1}, 1) = q_{3}
R_{21}^{(0) } = 0
because δ(q_{2}, 0) = q_{1}
R_{22}^{(0) } = ε
because from q_{2} we can reach q_{2} only on ε transition
R_{23}^{(0)} = 1
because δ(q_{2}, 1) = q_{3}
R_{31}^{(0)} = ɸ
because from q_{3} to reach q1 no such path exists
R_{32}^{(0)} = 0 + 1
because from q_{3} to reach q_{2} we can give either ‘0’ or ‘1’ as input symbol.
R_{33}^{(0)} = ε
to remain in q_{3} it needs ε transition.
Tabulation is as follows for K = 0:
R_{11}^{(0)}εR_{12}^{(0)}0R_{13}^{(0) }1R_{21}^{(0) }0R_{22}^{(0)}εR_{23}^{(0)}1R_{31}^{(0)}ɸR_{32}^{(0)}0 + 1R_{33}^{(0)}εWe need to apply the following simplification.
- (ε + R)* = R*
- R + RS* = RS*
- ɸR = Rɸ = ɸ (Annihilation)
- ɸ + R = R + ɸ = R (Identity)
Now we will go for K = 1
n = 3 (number of states is 3 {q_{1}, q_{2}, q_{3}})
R_{ij}^{(K)} = R_{ij}^{(K}^{−}^{1)} + Ri_{K}^{(K}^{−}^{1)}(R_{KK}^{(K}^{−}^{1)})*R_{Kj}^{(K}^{−}^{1)}
Therefore for K = 1
R_{11}^{(1) } = R_{11}^{(0)} + R_{11}^{(0)}(R_{11}^{(0)})* R_{11}^{(0)}
= ε + ε(ε)*ε= εR_{12}^{(1)} = R_{12}^{(0)} + R_{11}^{(0)}(R_{11}^{(0)})* R_{12}^{(0)}
= 0 + ε(ε)*0= 0 + 0 = 0R_{13}^{(1)} = R_{13}^{(0)} + R_{11}^{(0)}(R_{11}^{(0)})* R_{13}^{(0)}
= 1 + ε(ε)*1= 1 + 1 = 1R_{21}^{(1)} = R_{21}^{(0)} + R_{21}^{(0)}(R_{11}^{(0)})* R_{13}^{(0)}
= 0 + 0(ε)*ε= 0 + 0 = 0R_{22}^{(1)} = R_{22}^{(0)} + R_{21}^{(0)}(R_{11}^{(0)})* R_{12}^{(0)}
= ε + 0(ε)*0= ε + 00R_{23}^{(1)} = R_{23}^{(0)} + R_{21}^{(0)}(R_{11}^{(0)})* R_{13}^{(0)}
= 1 + 0(ε)*1= 1 + 01R_{31}^{(1)} = R_{31}^{(0)} + R_{31}^{(0)}(R_{11}^{(0)})* R_{11}^{(0)}
= ɸ + ɸ(ε)*ε= ɸ + ɸ= ɸR_{32}^{(1)} = R_{32}^{(0)} + R_{31}^{(0)}(R_{11}^{(0)})* R_{12}^{(0)}
= 0 + 1 + ɸ(ε)*)= 0 + 1R_{33}^{(1)} = R_{33}^{(0)} + R_{31}^{(0)}(R_{11}^{(0)})* R_{13}^{(0)}
= ε + ɸ(ε)*1= εTabulation is as follows for K = 0:
R_{11}^{(1) }εR_{12}^{(1) }0R_{13}^{(1) }1R_{21}^{(1) }0R_{22}^{(1) }ε + 00R_{23}^{(1) }1 + 01R_{31}^{(1) }ɸR_{32}^{(1) }0 + 1R_{33}^{(1) }εNow for K = 2
R_{ij}^{(1)} = R_{ij}^{(2}^{−}^{1)} + R_{i}_{2}^{(2}^{−}^{1)}(R_{22}^{(2}^{−}^{1)})* R_{2}_{i}^{(2}^{−}^{1)}
= R_{ij}^{(1)} + R_{i}_{2}^{(1)}(R_{22}^{(1)})* R_{2}_{i}^{(1)}Therefore
R_{11}^{(2)} = R_{11}^{(1)} + R_{12}^{(1)}(R_{22}^{(1)})* R_{21}^{(1)} = ε + 0(ε + 00)*0
= ε + 0(00)*0 = (00)*R_{12}^{(2)} = R_{12}^{(1)} + R_{12}^{(1)}(R_{22}^{(1)})* R_{22}^{(1)} = 0 + 0(ε + 00)*(ε + 00)
= 0 + 0(00)* = 0(00*) (∴R + RS* = RS*)R_{13}^{(2)} = R_{13}^{(1)} + R_{12}^{(1)}(R_{22}^{(1)})* R_{23}^{(1)} = 1 + 0(ε + 00)*(1 + 01)
Here (ε + 00)* = (00)*
and (1 + 01) = (ε + 0)1
and so R_{13}^{(2)} = 1 + 0(00)*(ε + 0)1
Here (00)*(ε + 0) = 0*
Hence 0(00)*(ε + 0)1 = 0(0*)1
∴ R_{13}^{(2)} = 1 + 00*1 = 0*1
R_{21}^{(2)} = R_{21}^{(1)} + R_{21}^{(1)}(R_{12}^{(1)})* R_{21}^{(1)}
= 0 + (ε + 00)(ε + 00)*0= 0 + 00(00)*0= 0(00)*R_{22}^{(2)} = R_{22}^{(1)} + R_{22}^{(1)}(R_{22}^{(1)})* R_{22}^{(1)}
= (ε + 00) + (ε + 00)(ε + 00)*(ε + 00)= (00)*R_{23}^{(2)} = R_{23}^{(1)} + R_{22}^{(1)}(R_{22}^{(1)})* R_{23}^{(1)}
= (1 + 01) + (ε + 00)(ε + 00)*(1 + 01)= (ε + 0)1 + (00)*(1 + 01)= (ε + 0)1 + (00)*(ε + + 0)1= (ε + 0)1 + 0*1 (because (00)*(ε + 0)1 = 0*1)= 0*1R_{31}^{(2)} = R_{31}^{(1)} + R_{32}^{(1)}(R_{22}^{(1)})* R_{21}^{(1) }
= ɸ + (0 + 1)(ε + 00)*0= ɸ + (0 + 1)(00)*0= (0 + 1)(00)*0 (because (ε + 00)* = (00)*)R_{32}^{(2)} = R_{32}^{(1)} + R_{32}^{(1)}(R_{22}^{(1)})* R_{22}^{(1)}
= (0 + 1) + (0 + 1)(ε + 00)*(ε + 00)= (0 + 1) + (0 + 1)(00)*= (0 + 1)(00)* (because R + RS* = RS*)R_{33}^{(2)} = R_{33}^{(1)} + R_{32}^{(1)}(R_{22}^{(1)})* R_{23}^{(1)}
= ε + (0 + 1)(ε + 00)*(1 + 01)= ε + (0 + 1)(00)*(ε + 0)1 (because (ε + 00)* = (00)* and (1 + 01) = ((ε + 0)1))= ε + (0 + 1)0*1 (because (00)*(ε + 0) = 0*)= ε + (0 + 1)0*1Tabulation is as follows for K = 0:
R_{11}^{(2)}(00)*R_{12}^{(2) }0(00)*R_{13}^{(2)}0*1R_{21}^{(2)}0(00)*R_{22}^{(2) }(00)*R_{23}^{(2)}0*1R_{31}^{(2)}(0 + 1)(00)*0R_{32}^{(2)}(0 + 1)(00)*R_{33}^{(2)}ε + (0 + 1)0*1No we will find regular expression L(M)
L(M) = R_{1j}^{(n)}
i.e., R_{1}_{j}_{1}^{(n)} + R_{1}_{j}_{2}^{(n)} + …. + R_{1}_{jp}^{(n) }
Where F is set of final sets
F = {q_{j}_{1}, q_{j}_{2}, … q_{jp}}
In our example, the set of final states
F = {q_{2}, q_{3}}
∴ L(M)= R_{12}^{(3)} +R_{13}^{(3)} (where n =3 states)
∴R_{12}^{(3)} = R_{12}^{(2)} +R_{13}^{(2)}(R_{33}^{(2)})*R_{32}^{(2)}
= 0(00)*+0*1(ε+(0+1)0*1)*(0+1)(00)*
= 0(00)*+ 0*1((0+1)0*1)*(0+1)(00)*(because (ε+R)*=R*)
R_{13}^{(3)} =R_{13}^{(2)} +R_{13}^{(2)}(R_{33}^{(2)})*R_{33}^{(2)}= 0*1+0*1(ε+0+1)0*1*(ε+(0+1)0*1)Similarly =0*1[ε+(ε+(0+1)0*1)*(ε+(0+1)0*1)]= 0*1(ε+(0+1)0*1)*(because ε+R*=R*)= 0*1((0+1)0*1)*(because ε+R)*=R*)R_{12}^{(3)} = R_{13}^{(2)}= 0*1((0+1)0*1)*(0+1)(00)*+0(00)* +0*1((0+1)0*1)*= 0*1((0+1)0*1)*(0+1)(00)*+0(00)*(because R + RS*= RS*)∴ The regular expression for the finite automata is
L(M) = 0*1((0 + 1)0*1)(0 + 1)(00)* + 0(00)*
- Prove that a CFL can be recognized by a PDA by empty stack. (9)
Ans: Theorem
For any context free language L, there exists an pda M such that L = L(M)
Proof
Let G = (V, T, P, S) be a grammar. There exists a Greibach Normal Form then we can construct pda which simulates left most derivations in this grammar.
M = (Q, ∑, ϒ, δ, q0, z, F), where
Q = {q_{0}, q_{1}, q_{f}} = set of states
∑ = terminals of grammar G
ϒ = V∪{z} where V is the variables in grammar G
F = {q_{f}} = final state.
The transition function will include
δ(q_{0}, λ, z) = {q_{1}, Sz}, so that after the first move of M, the stack contains the start symbol S of the derivation. (The stack symbol z is a marker to allow us to detect the end of the derivation)
In addition, the set of transition rules is such that
- δ(q_{1}, λ, A) = {(q, α)} for each A→α in P
- δ(q, a, a) = {(q, λ)} for each a∈∑
- Construct a PDA equivalent to the following grammar.
S→ aAA A → aS | bS |a (7)
Ans: S→aAA
A→aS|bS|a
The PDA equivalent of the given grammar is:
M = ({q}, (a, b), {S, a, b, A}, δ, q, S, ɸ) where δ is defined as:
R_{1}: δ(q,λ,S ) = {(q,aAA )}
R_{2 } : δ (q,λ,A ) = {(q,aS),(q,bS),(q,a)}
R_{3} : δ(q,a,a) = {(q,λ)}
R_{4 }: δ(q,b,b) = {(q,λ)}
Test whether some string abaaaa is in N(M).
(q, abaaaa, S ) (q, a baaaa, aAA) by R_{1}
(q, baaaa, AA) by R_{1}(q, baaaa, bSA) by R_{2}(q, aaaa, SA) by R_{4}(q, aaaa, aAAA) by R_{1}(q, aaa, AAA) by R_{3}(q, aaa, aAA) by R_{2}(q, aa, aA) by R_{2}(q, a, A) by R_{1}(q, a, a) by R_{2}(q, l, l) by R_{3} - Prove that every language recognized by a PDA is Context-Free. (8)
Ans: Theorem
If L is N(M) for some PDA M, then L is CFL.
Proof
- It has single final state q_{f} iff the stack is empty.
- All transitions must have the form
δ(q_{i}, a, A) = {C_{1}, C_{2}…..C_{n}}, where
δ(q_{i}, a, A) = (q_{j}, λ) (1)
δ(q_{i}, a, A) = (q_{j}, BC) (2)
That is, each move either increases or decreases the stack content by a single symbol.
Given M = (Q, ∑, ϒ, δ, q_{0}, z_{0}, {q_{f}}) satisfies the condition (1) and (2)
G = (V, T, P, S)
V = elements of the form [a, A, p], a and p in Q and A in ϒ
T = ∑
S = start symbol
S → [q_{0}, z_{0}, q] for each q in Q.P consist of: u, v∈∑*
A, X ∈ ϒ*, q_{i}, q_{j}∈Q(q_{i}, uv, AX)(q_{j}, v, X)
Implies that (q_{i}, A, q_{j})→u
Consider [q_{i}, A, q_{k}]→a[q_{j}, B, q_{i}] [q_{i}, C, q_{k}]
The corresponding transition for PDA is
δ(q_{i}, a, A) = {(q_{j}, B C)……}
Similarly if [q_{i}, A, q, ] →a then the corresponding transition is δ(q_{i}, a, A) = {(q_{j}, λ)} For all sentential forms leading to a terminal string, the argument holds true.
The conclusion is
(q_{0}, w,z_{0} ) | − * (q_{j} , λ, λ) is true iff (q_{0}z_{0}q_{f})w
Consequently L(M) = L(G)
- Construct a PDA for the set of palindrome over the alphabet {a, b}. (8)
Ans:
M = (Q,Σ,Г,d,q_{0},z, F) where
Q = {q_{0},q_{1},q_{2}}
Σ = {a,b}
Г = {z,a,b}
F = {q_{2}}
The transition function has several parts :
- set to push w on to stack.
δ(q_{0},a,a) = {(q_{0},aa)}→(1)
δ(q_{0},b,a) = {(q_{0},ba)}→(2)
δ(q_{0},a,b) = {(q_{0},ab)}→(3)
δ(q_{0},b,b) = {(q_{0},bb)}→(4)
δ(q_{0},a,z) = {(q_{0},az)}→(5)
δ(q_{0},b,z) = {(q_{0},bz)}→(6)
- To find middle of the string, where npda switches from q_{0} to state q_{1}.
δ(q_{0},λ,a) = {(q_{1},a)}→(7)
δ(q_{0},a,b) = {(q1,b)}→(8)
- Set to match w^{R} against contents of the stack.
δ(q_{1},a,a) = {(q_{1},λ)}→(9)
δ(q_{1},b,b) = {(q_{1},λ)}→(10)
and finally
δ(q_{1},λ,z) = {(q_{2},z)}→(11)
To recognize successful match.
The processing of string w = abba
( q_{0},abba, z )|−( q_{0},bba,az ) → by rule 5
|−( q_{0},ba,baz ) → by rule 2|−( q_{1},ba,baz ) → by rule 8|−( q_{1},ba,baz ) → by rule 8|−( q_{1},a,az ) → by rule 10|−( q_{1},a,az ) → by rule 9|−( q_{1},λ,z ) → by rule 9|−( q_{2},λ ) → by rule 11
Hence string is accepted.
Note:
At 3^{rd} move, to locate middle of the string, (q_{0}, bc, baz) we have two choices for next move
- δ(q_{0}, b, b) = {(q_{0}, bb)} (or)
- δ(q_{0}, λ, b) = {(q_{1}, b)}
- set to push w on to stack.
- Prove that every non-empty CFL is generated by a CFG with no useless symbols. (9)
Ans: Theorem
If G is a CFG such that L(G) = ɸ, we can find an equivalent grammar G^{1}, such that each variable in G^{1} derives some terminal string.
Proof:
Let G = (N, T, S, P) and G^{1} = (N^{1}, T^{1}, S, P^{1})
- Construction of N^{1}
We define W_{1 }⊆ N by recursion. W_{1} = {A∈N| there exists a production A→w where w∈T*}. (If W1 = ɸ, some variable will remain after the application of any production, and so L(G) = ɸ).
W_{i} + _{1} = W_{i}∪{A∈N| there exists some production A→α with α∈ (T∪W_{i})*}
- Construction of i
Pi = {A→α ׀ A, α ∈(Ni∪T)*}
We can define Gi = (Ni, T, S, Pi), S is in Ni. We can prove that every variable In Ni defines some terminal string. So S ∈Ni, L(G) = ɸ. Now we prove that Gi is the required grammer.
- If each A ∈ Ni than A w for sme w ∈ T*; conversely, if A w then A∈Ni
- L(Gi) = L(G)
To prove (i) we note that W_{k} + _{1} W_{2} ∪ ∪ W_{k.}. _{We} prove by induction on i
That for i = 1, 2, … k, A ∈ Wi implies A w for some w ∈ T*. If A∈W_{1}, then A w.So the production w is in P^{1}.Therefore, A w. Thus there is basis for induction.
_{*}Let us assume the result for i. Let A∈W_{i} + _{1}. Then either A ∈ w_{i}, in which case, A w for some w∈T* by induction hypothesis. Or, there exists a production A→α is P^{1}. e can write α = X_{1} X_{2}….X_{m}, where X_{j}∈T∪W_{i}. If X_{j}∈W_{i} by induction hypothesis, X_{j } G W_{j} for some W_{j} ∈X_{j}). By induction the result is true for i = 1, 2, …...K.
The converse part can be proved in a similar way by induction on the number of steps in the derivation A w. We see immediate;y that L(G_{1}) ⊆ L(G) as N_{1 }⊆ N and P_{1 }⊆ P.
To prove L(G)⊆L(G^{1}), we need an auxillary result.
A w if A w for some w∈T* → 1
We prove the above step by induction on the number of steps in the derivation A w If Aw, then A→w is in P and A∈W^{1}⊆N^{1}. As A∈N^{1} and w∈T*, A→w is in P^{1}. So A w, and there is a basis for induction. Assume A w derivation in atmost k steps. Let A w. We can split this as
A X_{1 }X_{2}….X_{m} A w_{1}w_{2}….wm such that X_{j }w_{j}. If X_{j}∈T then w_{j} = x_{j} → 2
If X_{j}∈N then by equation 1 above, X_{j}∈N^{1}. As X_{j } w_{j} is atmost k steps, X_{j } Also, X_{1}, X_{2}, ……X_{m} ∈(T∪N^{1})* implies A→X_{1}, X_{2}, …X_{m} is in P^{1}. Thus A X_{1}, X_{2} …..X_{m} w_{1}w_{2}….w_{m}. Hence by induction, equation 1 is true for all derivations. In particular, S w implies S w. This prove that L(G)⊆L(G^{1}), and equation 2 is completely proved.
- Construction of N^{1}
- State and prove Chomsky normal form for CFL. (7)
Ans: Theorem
For every context free grammar, there is an equivalent grammar in Chomsky Normal Form (CNF)
Step 1: Elimination of null productions. We then apply theorem to eliminate chain productions. Let the grammar thus obtained to G = (N, T, S, P)
Step 2: Elimination of terminals on R.H.S. We define G1 = (N^{1}, T, S, P_{1}) where P_{1} and N^{1} are constructed as follows:
- All the productions in P of the form A→a or A→BC are included in P_{1}, All the variables in N are included in N^{1}.
- Consider A→X_{1}, X_{2}…..X_{n} with some terminal on R.H.S. If X_{i} is a terminal, say a_{i}, add a new variable C_{ai} to N^{1} and C_{ai}→_{ai} to P_{1}. In production A→X_{1} X_{2}….X_{n}, every terminal on R.H.S. is repaced by the corresponding new variable and the variables on the R.H.S. are retained. The resulting production is added to P_{1}. Thus we get G_{1 } = (N^{1}, T, P_{1}, S).
Step 3: Restricting the number of variables on R.H.S. For any production in P_{1}, the R.H.S. consists of either a single terminal (or λ in S→λ) or two or more variables.
We define G_{2} = (N″, T, P_{2}, S) as follows:
All the productions in P_{1} are added to P_{2} if they are in the required form. All the variables in N1 are added to N″.
Consider A→A_{1} A_{2}….A_{m}, where m≥3. We introduce new productions A→A_{1}C_{1}, C_{1}→A_{2}C_{2}, …C_{m}_{−}_{2}→A_{m}_{−}_{1}A_{m}, and new variables C_{1}, C_{2}, …..C_{m}_{−}_{2}. These are added to P″ and N″ respectively.
Thus we get G_{2} in Chomsky Normal Form.
Step 4: To complete the proof we have to show that L(G) = L(G_{1}) = L(G_{2}).
To show that L(G)⊆L(G_{1}), we start with w∈L(G). If A → X_{1}, X_{2} …..X_{n} is used in the derivation of w, the same effect can achieved by using the corresponding production in P, and the productions involving the new variables. Hence A X_{1}X_{2}….X_{n}. Thus L(G)⊆L(G_{1}).
Let w ∈ L(G_{1}). To show that w∈L(G_{1}), it is enough to prove the following.
A w if A∈N, A w (1)We prove 1 by induction on the number of steps in A w If A w, the A→w is a production in P_{1}. By construction of P_{1}, w is a single terminal. So A→w is in P i.e., A w. This is basis for induction.
Let us assume (1) for derivations in at most k steps. Let A w. we can split this derivation as A A_{1}A_{2}….A_{m } w_{i}, w_{m} = w such that A_{i} w_{i}. . Each A_{i} is either in N or a new variable, say Ca_{i}, When A_{i}∈N, A_{i} w_{i} is a derivation in atmost k steps, and so by induction hypotheses, A_{i} w_{i}. Thus (1) is true for all derivations. Therefore L(G) = L(G_{1}).
The effect of applying A→A_{1}A_{2}….Am in a derivation for w ∈ L(G_{1}) can be achieved by applying the production A→A_{1}C_{1}, C_{1}→A_{2}C_{2}, ……C_{m}_{−}_{2}→A_{m}_{−}_{1}A_{m} in P_{2}.
Hence it is easy to see that L(G_{1})⊆L(G_{2}).
To prove L(G_{2})⊆L(G_{1}), we can prove an auxillary result.
A w if A∈N^{1}, A w (2)
Condition (2) can be proved by induction on the number of steps A w. Applying (1) to S, we get L(G_{2})⊆L(G_{1}).
Thus L(G) = L(G_{1}) = L(G_{2})
- State and prove pumping lemma for context free languages (10)
Ans: Theorem
Let be an infinite context-free language. Then there exists some positive integar m such that any w ∈ L with |w|≥m can be decomposed as
w = uvxyz (1)
with
|vxy|≤m (2)
and
|vy|≥1 (3)
such that
uv^{1}xy^{1}z∈L (4)
for all i = 0, 1, …… This is known as pumping lemma for context free languages.
Proof
Consider the context free grammar G without unit productions (or)λ-productions. L−{λ} is the language which is generated by G. The length of the string on the right hand side of any production is bounded. Since L is infinite, there exists arbitrarily long derivations and corresponding derivation trees of arbitrary height.
Consider a high derivation tree from root to leaf. Since the number of variables in G in finite, there must be some variables that repeats on this path.
Consider the derivation
S⇒^{*}uAz⇒^{*}uvAyz⇒^{*}uvxyz
Where u, v, x, y, z are all strings of terminals.
A⇒^{*}uAy and A⇒^{*}x.
If this derivations are repeated, we can generate all strings uv^{1}xy^{1}z, i = 0, 1….
We can assume that no variables repeats (repeating variable-A). The length of the strings v, x, and y depends only on productions of the grammar and can be bounded independently of w (condition (2) holds). Since there is no λ-productions, v and y cannot be empty string (condition (3) holds).
- Using pumping lemma prove that the language (a^{i}b^{i}c^{i }ǀ≥1) is not context free.(6)
Ans: The given language L = {a^{n} b^{n} c^{n}}
Let z be any string that belongs to L
Let z = a^{P}b^{P}c^{P}∈L
According to pumping lemma, if z is in L and |z|>n, z can be written as
z = uvwxy
z = a^{P}b^{P}c^{P} as
u, vwx and y respectively, we get
u = a^{P }
vwx = b^{P }where |vwx|≤n
vx = b^{P}^{−}^{m }where |vx|≥1
y = c^{P}
Substituting these values in uv^{1}wx^{1}y
= uv^{i}^{−}^{1}vwx x^{i}^{−}^{1}y (uv^{i}wx^{i}y is expressed in this form)
= uvwx(vx)^{i}^{−}^{1}y
= a^{P}b^{P}(b^{P}^{−}^{m})^{i}^{−}^{1}c^{P}
= a^{P}b^{P}b^{P}^{1}^{−}^{mi}^{−}^{P} + ^{m}c^{P}∉L for all values of i
Let i = 0.
uv^{i}^{−}^{1} vwx x^{i}^{−}^{1} y = a^{P}b^{P}b^{P}^{(0)}^{−}^{m}^{(0)}^{−}^{P} + ^{mi}c^{P}
= a^{P}b^{P}b^{m}^{−}^{P}c^{P}
= a^{P}b^{m}c^{P}L
Hence L is not a context free grammar.