Appendix B: Frequently Asked University Questions with Solutions – Formal Languages and Automata Theory

Appendix B

FREQUENTLY ASKED UNIVERSITY QUESTIONS WITH SOLUTIONS

PART A - Brief Questions

  1. 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”

    1. We assume P and Not Q.
    2. We arrive at some conclusion contradicting one of our assumptions, or something obviously untrue for Not Q.
    3. This contradicts our assumption for P and Not Q.
  2. 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 (q0) = {q0, q1, q2}

    ε-closure (q1) = {q1, q2}

    ε-closure (q2) = {q2}

  3. Construct NFA for the regular expression a*b*.

    Ans:

  4. 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.

  5. 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.
  6. Define parse tree with an example.

    Ans: A tree is a parse \ derivation tree for G if:

    1. Every vertex has a label which is a symbol of VU TU{∅}.
    2. The label of the root is S.
    3. If a vertex is interior and has a label A, then A must be in V.
    4. If n has a label A and vertices n1, n2, ….. nk are the sons of the vertex n in order from left with labels X1, X2, ………..Xk respectively then A→ X1X2…..Xk must be in P.
    5. If vertex n has label ε, then n is a leaf and is the only son of its father.
  7. 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:

    1. |VX| > = 1
    2. |VWX| < = n and
    3. for all i> = 0 UViWXiY is in L.
  8. 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:

    1. Non terminal → string of exactly two Nonterminals i.e. A → BC
    2. Non terminal → one terminal i.e A → a
  9. 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).
  10. What is recursively enumerable language?

    Ans:

    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).
  11. 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, ∑, δ, q0, F)

    Where Q = Non empty finite set of states

    ∑ = input alphabet

    q0 = 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: δ(q1, a) = q2

  12. 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).

  13. 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)*.

  14. Name any four closure properties of Regular languages.

    Ans: The principal closure properties of regular languages are:

    1. The union of two regular languages is regular.

      If L and M are regular languages, then so is L ∪ M.

    2. The intersection of two regular languages is regular.

      If L and M are regular languages, then so is L ∩ M.

    3. The compliment of two regular languages is regular.

      If L is a regular language over alphabet Σ, then Σ*-L is also regular language.

    4. The difference of two regular languages is regular.

      If L and M are regular languages, then so is L − M.

  15. 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)*.

  16. 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.

  17. 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*.

  18. 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.

  19. 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.

  20. 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.

  21. 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

  22. What is a non deterministic finite automation?

    Ans: Nondeterministic finite automata can be defined as quintuple M = (Q, ∑, δ, q0, F)

    Where Q = Non empty finite set of states

    ∑ = input alphabet

    q0 = 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 ∑ →2Q

  23. 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, UViW is in L.

  24. 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.

  25. Write the CFG for the language L = {an bn | n1}.

    Ans: The Given language is an(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
  26. 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, ∑, δ, q0, F}where strings are as {w | (q0, w) qf} 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, ∑, Γ, δ, q0, Z0, F}where strings are as {w | (q0, w, Z0) (qf, ε, Z0)} i.e it reaches to at least one final state.

  27. 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.

  28. List out the different techniques for Turing machine construction.

    Ans: The different techniques for Turing machines are

    1. Storage in Finite Control
    2. Check off symbol
    3. Shifting over
    4. Multi track tape
    5. Subroutine
  29. What are (a) recursively enumerable languages (b) recursive sets?

    Ans:

    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). Recursive sets consists set of strings that are accepted by the Turing machine.
  30. What is Universal Turing machines?

    Ans: A universal Turing machine, Mu 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 Mu 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}, δ, q1, B, q2) where

    Q = {q1, q2, ………………qn} and q1 the initial state, q2 the single final state. The alphabet {0, 1, B} ∈ Γ are represented as a1, a2 and a3. The direction left and right are represented as D1 and D2 respectively. The transitions of TM are encoded in special binary representation where each symbol is separated by 1.

  31. Construct deterministic finite automata to recognize odd number of 1’s and even number of 0’s?

    Ans:

  32. State the relations among regular expression, deterministic infinite automaton, non deterministic finite automaton and finite automaton with epsilon transition.

    Ans:

    NFA – Non deterministic Finite Automata.

    DFA – Deterministic Finite Automata.

  33. 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*

  34. Prove or disprove that the regular languages are closed under concatenation and complement.

    Ans: Concatenation: Let A = (Q, Σ, δ, q0, F) where

    Q = Q1 ∪ Q2, Σ = Σ1 ∪ Σ2, q0 = q1, F = F2 and δ is defined as follows:

    δ(q, a) = {δ1 (q, a)} for each q in Q1−F1

    δ(q, a) = {δ1 (q, a)} for each q in F1

    and

    δ(q, a) = {δ2 (q, a)} for each q in Q2.

    A word w is in L1 L2 if w = w1 w2 where w1L1 and w2L2.

    This is equivalent to δ1(q1, w1) being F1 and δ2(q2, w2) being F2 which is equivalent to w1 w2 being in T(A). Thus L1 L2 = 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, δ, q0, 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, Σ, δ, q0, QF).

    The M′ accepts a word w if and only if is in QF, that is, w is in Σ*−X. Note that it is essential to the proof that M is deterministic and without y moves.

  35. Consider the following grammar G with productions

    SABC|BaB AaA|BaC | aaa BbBb|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→BaB
    A→aA|aaa
    B→bBb|a
  36. State the definition for Pushdown automata.

    Ans: A push down automaton M is defined by (Q, Σ, Γ, δ, q0, z0, 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.
    • q0 ∈ Q is the start state (or) initial state
    • z0 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}) × Γ*) → (2Q×Γ*)
  37. Convert the following grammer G in greibach normal form.

    S→ABb|a A aaA | B B bAb

    Ans: GNF (Solution):

    Replace S with A1, A with A2 and B with A3.

    A1A2 A3b | a
    A2aaA2A3
    A3 → b A2b

    Here A2 and A3 are useless symbols. Therefore the required GNF form is:

    A1a
  38. 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 ⊃ }
  39. 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.

  40. 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.

  41. 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.

  42. Construct a PDA to accept the language {(ab)n | n ≥ 1} empty stack.

    Ans: L = {ab; abab, ababab…}

    δ(q0, a, z0) = (q1, az0)
    δ(q1, b, a) = (q0, ∅)
    δ(q0, λ, z0) = (q2, λ)
  43. 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.

  44. Give a semi-Thue grammar generating (ai|i is a positive power of 2).

    Ans: Give a semi-The grammar generating {ai| i is a positive power of 2).

    SACaB, CaaaC, CBDB, CBE, aDDa,
    ADAC, aEEa, AE→ε
  45. What is {10, 11}* (Write atleast first seven terms)

    Ans: (ε, 10, 11, 1011, 101011, 101111, 111110, …)

  46. State Greback Normal From.

    Ans: A context free grammar G is in GNF if every production is of the form Aaa 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.

  47. For a PDA M = (Q, Σ, ϒ, δ, q0, Z0, F), define the language accepted by final state.

    Ans: Let M = (Q, ∑, ∈, δ, q0, Z0, 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.

  48. 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 L1 ≤ PL for every L1 ⊆ NP. The language L is NP-complete if L ⊆ NP and L is NP-hard.

  49. 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 |wm can be decomposed as

    w = uvxyz        (1)

    with

    |vxy|≤m        (2)

    and

    |vy|≥1        (3)

    Such that

    uvixyiz ∈ L        (4)

    for all i = 0, 1, … This is known as pumping lemma for context free languages.

  50. State two languages, which are not recursively enumerable.

    Ans: State two languages, which are not recursively enumerable.

    1. The diagonalization language Ld is the set of string wi, where wi ∉ L(Mi)
    2. The language NSA (Not Self Accepting)
  51. List any four ways of theorem proving

    Ans:

    1. Deductive proofs
    2. Proof about sets
    3. Proof by contradiction
    4. Proof by counter example
  52. Show that the complement of a regular language is also regular.

    Ans: Let L = L(A) for the DFA A = (α, Σ, δ, q0, F)

    then = L(B ) where B is a DFA and B = (α, Σ, δ, q0, F)

    B = (α, Σ, δ, q0, 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)

  53. 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.

  54. 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.

  55. 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 | ∈

  56. Find whether the language {am, bm, cm/m {0} is CFL or not.

    Ans: Let z = anbncn

    Then |z| = |anbncn| = 3n

    Let ‘n’ be the number defined in pumping lemma.

    |z| = 3n >n

    As 0 ≤ |νx| ≤ n, ‘ν’ or ‘x’ cannot contain all the three symbols of a, b, c So, ‘ν’ or ‘x’ is of the form

    1. a’s
    2. b’s
    3. c’s
    4. aibi
    5. bici

    Then uviuxiy

    Let i = 0, u = ai, v = bj
    z = uv0wxcy – uwy

    ∴ uwy contains atmost ai, bn-j, cn, which is not of the form uvi wxi y

    ∴ uwy ∉ L

    ∴ L is not content free.

  57. 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}

  58. 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.

  59. 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.

  60. Define diagonal language

    Ans: The language Ld consists of all those strings ‘w’ such that the Turing Machine represented by ‘w’ does not accept the input ‘w’

    Ld = {wcwc ∉ L(Mi)}
  61. 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.,

    1. Control mechanism of Elevator
    2. Working Principle of Digital Logic Circuit.
    3. Operation of washing Machine.
  62. Enumerate the differences between DFA and NFA.

    Ans:

    DFA
    NDFA

    The future/behaviour of the system can be determined uniquely.

    The future/behaviour of the system can’t be determined uniquely

    δ : Q × Σ → Cα

    δ : Cα × Σ → 2

    δ(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

  63. Verify whether L = a2n / n ≥ I} is regular.

    Ans:

    1. Assume that L is regular.

      Let ‘n’ be the number of states in FA accepting L.

    2. Let z = a2n.

      Then |Z| = 2x > x

      By PL, z = uvw with |uv| ≤ x & |v| > 0

    3. Let I = 2 is uviw

      Then |uv2w| = |uvw.v|

      As |uv2w| = |uvw| + |v|

      = 2x + x
      = 3x ≠ 2x

      i.e., ‘a’ increases is proves of 2x not in 3x

      ∴ uv2w ∈ L, which is a contradiction.

    Hence L is not regular.

  64. Mention the closure properties of regular languages.

    Ans:

    • Union
    • Intersection
    • Complement
    • Difference
    • Reversal
    • Closure
  65. 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:

  66. Define the languages generated by a PDA Using the two method of accepting a language.

    Ans: Let M = (Q, Σ, Г, δ, qe, Z0F) be a PDA. Then the language accepted by a final store is denoted by L(M), defined as

    L(M) = {ω/(q0, ω, z0) (P, ∈, v) for serve P ∈ F, v ∈ Г*}

    Let M = (Q, Σ, Г, δ, q0, Ze, F = ɸ) be PDA. Then the language accepted by a empty stack/null stack is denoted by N(M), is defined as,

    N(M) = {ω/(q0, ω, z0) (P, ∈, ∈) / (P, ∈, Z0) for serve P ∈ Q}

  67. 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| ≤ x

    For all i ≥ 0, uviwxiy ∈ L

  68. Define a Turning Machine.

    Ans: A Turning Machine M = (α, Σ, Г, δ, q0, B1F)

    Where

    Q - finite set of states.

    Г - set of tape symbols, tape alphabet

    Σ - set of input symbols, input alphabet

    q0 ∈ cα the initial state

    BГ called black symbol.

    Fcα 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.

  69. Differentiate between recursive and recursively enumerate languages.

    Ans:

    Recursive
    Recursively Enumerate

    A 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.

  70. Mention any two undesirability properties of recursively enumerable languages.

    Ans:

    • Emptiness
    • Finiteness
    • Regularity
    • Content free.

PART B - Detailed Questions

  1. 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

    1. P(0) and
    2. 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)

  2. 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 2n states where as NFA has only n states.
  3. Construct NFA without ε - transitions for the NFA given below.

    Ans: The transition table is

    Step 1: Find ε-closure of each state.

    ε-closure (q0) = {q0, q1}
    ε-closure (q1) = {q1}

    Step 2: Find the transition on each state for each element.

    (q0, 0) = ε-closure (δ(ε-closure (q0), 0))
    = ε-closure (δ({q0, q1 }, 0))
    = ε-closure ({q0}, ∪{∅})
    = {q0, q1 }
    (q0, 1) = ε-closure (δ(ε-closure (q0), 1))
    = ε-closure (δ({q0, q1 }, 1))
    = ε-closure ({∅ }, ∪{ q1})
    = { q1 }
    (q1, 0) = ε-closure (δ(ε-closure (q1), 0))
    = ε-closure (δ({q1 }, 0))
    = ε-closure ({∅})
    = { ∅ }
    (q1, 1) = ε-closure (δ(ε-closure (q1), 1))
    = ε-closure (δ({q1 }, 1))
    = ε-closure ({ q1})
    = { q1}

    NFA without – ε transitions is

    a=0
    a=1
    →*q0
    {q0, q1 }
    {q1}
    *q1
    {q1}
  4. 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.

  5. 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=a
    a=b
    →q1
    q1
    q2
    q2
    q3
    q2
    q3
    q4
    q2
    *q4
    q1
    q2
    1. Initially we identify 0 – equivalence as ∏0 = {Q10, Q20} Where Q10 is set of final states & Q20 = Q − Q10 is set of non final states.

      Q10 = {q4}

      Q20 = {q1, q2, q3}

    2. Construct ∏1 from ∏0 identifying the equivalent states in { Q10, Q20}

      Q10 cannot be divided as it has only one state.

      Q20 has four states, we need to identify whether they are 1- equivalent.

      Compare q1, q2 on input a and b

      δ (q1, a) = q1

      δ (q2, a) = q3 both resultant states belong to Q20.

      δ(q1, b) = q2

      δ(q2, b) = q2 both resultant states belong to Q20.

      ⇒ q1 is 1- equivalent to q2

      Compare q1, q3 on input a and b

      δ(q1, a) = q1

      δ(q3, a) = q4 both resultant states belong to different sets in Π0.

      δ(q1, b) = q2

      δ(q3, b) = q2 both resultant states belong to Q20.

      ⇒ q1 is not 1- equivalent to q3

      ∴∏1 = {Q11, Q21, Q31}

      Where

      Q11 = { q4}

      Q21 = { q1, q2 }

      Q31 = { q3}

    3. Construct ∏ 2 from ∏ 1 identifying the equivalent states in {Q11, Q21, Q31}

      Q11 and Q31 cannot be divided as these have only one state.

      Q21 has two states, we need to identify whether they are equivalent.

      Compare q1, q2 on input a and b

      δ(q1, a) = q1

      δ(q2, a) = q3 both resultant states belong to different sets in Π1.

      δ(q1, b) = q2

      δ(q2, b) = q2 both resultant states belong to Q20.

      ⇒ q1 is not 2- equivalent to q2

      ∴∏2 = {Q12, Q22, Q32, Q42 }

      Where

      Q12 = { q4}

      Q22 = { q1 }

      Q32 = { q2}

      Q32 = { q3}

    4. We see that ∏2 is equal not equal to ∏1, and each set has only single state
      a=a
      a=b
      →q1
      q1
      q2
      q2
      q3
      q2
      q3
      q4
      q2
      *q4
      q1
      q2
  6. 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 r1 and r2 be two regular expressions with less than i operations that has FA M1 and M2 given as M1 = {Q1, Σ1, δ1, q1, {f1 }} and M2 = {Q2, Σ2, δ2, q2, {f2 }} To show that r formed using union operation as r = r1 + r2 has automaton M which accepts the language L(M1) U L(M2) and is shown below.

    M = {{Q1 U Q2 U {q0, f0}}, { Σ2 U Σ2}, δ, q0, {f0} } where δ is defined as

    1. δ(q0, ε) = { q1, q2 }
    2. δ(q, a) = δ1(q, a) for q in Q1 –{f1} and a in Σ1 U {ε}.
    3. δ(q, a) = δ2(q, a) for q in Q2 –{f2} and a in Σ2 U {ε}.
    4. δ(f1, a) = δ2(f2, a) = {f0}

    By inductive hypothesis there are no transitions out of the final states. Thus all moves of M1 and M2 are present in M. Any string x valid in M1 or M2 must be valid in M. For such a string there exists a path from q0 to f0. To prove this observe rule 1 which shows path from q0 to either q1 or q2. Since “x” is valid in either M1 or in M2 there exists path from q1 to f1 or from q2 to f2. By rule 2 and 3 all these transitions are also present in M. By rule there is a path from f1 and f2 to f0. Hence there is path from initial state to final state which indicates “x” is also valid in M.

    Case 2:

    Let r1 and r2 be two regular expressions with less than i operations that has FA M1 and M2 given as M1 = {Q1, Σ1, δ1, q1, {f1 }} and M2 = {Q2, Σ2, δ2, q2, {f2 }} To show that r formed using concatenation operation as r = r1 ∙ r2 has automaton M which accepts the language L(M1) ∙ L(M2) as shown below.

    M = { {Q1 U Q2 }, { Σ1 U Σ2}, δ, q1, {f2} } where δ is defined as

    1. δ(q, a) = δ1(q, a) for q in Q1 –{f1} and a in Σ1 U {ε}.
    2. δ(f1, ε) = {q2}
    3. δ(q, a) = δ2(q, a) for q in Q2 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 q1 to f2 where q1 is initial state and f2 is final state in M. To prove this observe rule 1 which shows path from q1 to f1 on “x” as is valid in M1 By rule 2 there is path from f1 to q2 on ε. Rule 3 includes path from q2 to f2 on string “y” Hence there is path from initial state q1 to final state f2 which is the concatenated string “x” and “y”. Since w = x.y, w is valid string in M.

    Case 3:

    Let r1 regular expression with less than i operations that has FA M1 given as M1 = {Q1, Σ1, δ1, q1, {f1 }}. To show that r formed using concatenation operation as r = r1* has automaton M which accepts the language L(M1) * as shown below.

    M = {{Q1 U {q0, f0}}, Σ1, δ, q0, {f0}} where δ is defined as

    1. δ(q0, ε) = δ(f1, ε) = { q1, f0}
    2. δ(q, a) = δ1(q, a) for q in Q1 –{f1} 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 M1 For such a strings there exists a path from q0 to f0 . If string is ε then there is path from q0 to f0 using rule 1. For string’s x or xx the path is from q0 to q1 on ε followed by path on x from q1 to f1 using rule 2(if the string x is repeated then followed by a path on ε from f0 to q1 to repeat the string) followed by path on ε from f1 to f0 using rule 1. Hence L(M) = L(M1) *.

  7. Which of the following languages is regular? Justify.
    1. L = {anbm | 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.

    2. L = {anbn | n 1 }

      Ans: Let us assume that the language is regular. According to Pumping lemma choose the string Z = anbn 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, UViW ∈ 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 = ax Such that x ≥ 1.

    Let i = 0, then the string formed is UW, the string would be of the form an-x bn ∉ 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 = bx Such that x ≥ 1.

    Let i = 0, then the string formed is UW, the string would be of the form anbn-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 = axbx Such that x ≥ 1.

    If i = 0, then the string formed is UW, the string would be of the form an-xbn-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-xaxbxbn-x ∈ L as the number of a’s is equal to number of b’s.

    Now if i = 2, then the string formed is UV2W, the string would be of the form an-xaxbxaxbxbn-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.

  8. Obtain the regular expression for the finite automata.

    Ans: The set of equations that can be framed are

    q1 = q1 a + ε -1
    q2 = q1 b + q2 a -2
    q3 = q2 b -3

    Equation 1 is in the required form to apply the Arden’s theorem.

    q1 = q1 a + ε
    q1 = ε (a)*

    Substituting the expression of q1 in equation 2 we get

    q2 = (a)*b + q2 a
    q2 = (a)*b (a)*

    Substituting the expression of q2 in equation 3 we get

    q3 = (a)*b (a)*b

    The regular expression for the given DFA is (a)*b (a)*b

  9. 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 * id

    RMD: for string id + id * id is

    E E * E
    E * id
    E + E * id
    E + id * id
    id + id * id

    Parse trees represented by above LMD and RMD are as follows:

    As there are more than one parse tree, grammar is ambiguous.

  10. Find the context free language for the following grammars
    1. 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 | Na(w) = Nb(w) }

      This can be proved by mathematical induction.

    2. 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 = {anbn | n ≥ 1 }

      This can be proved by mathematical induction.

  11. Construct the PDA for L = {wwr | 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 q0 be initial state, qf be final state and Z0 be bottom of the stack.

    δ(q0, a, Z0) = (q0, aZ0)
    δ(q0, b, Z0) = (q0, bZ0)
    δ(q0, a, a) = (q0, aa), (q1, ε)
    δ(q0, b, b) = (q0, bb), (q1, ε)
    δ(q0, a, b) = (q0, ab)
    δ(q0, b, a) = (q0, ba)
    δ(q1, a, a) = (q1, ε)
    δ(q1, b, b) = (q1, ε)
    δ(q1, ε, Z0) = (qf, Z0)

    The final PDA is given by M = {(q0, q1, qf), (a, b), (a, b, Z0), δ, q0, Z0, qf}.

  12. 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 (
  13. Find GNF for the grammar

    SAA | 1

    ASS | 0

    Ans:

    S → AA | 1 ……..(1)
    A → SS | 0 ……..(2)

    Apply lemma 1 for (2)

    A→ AAS | 0S | 1

    Apply lemma 2 for this

    A→ 1S | 0 | 1S Z | 0Z

    Z → AS | ASZ substitute for A now in Z.

    Z→ 1SS | 0S | 1SSZ | 0SZ | 1SZSZ | 1SZS | 0ZS | 0ZSZ

    The grammar in GNF is as follows

    S → 1 | 1SA | 0A | 1SZA | 0ZS
    A → 1S | 0 | 1SZ | 0Z
    Z → 1SS | 0 S | 1SSZ | 0SZ | 1SZSZ | 1SZS | 0ZS | 0ZSZ
  14. 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, Σ, Г, δ, [q0, 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].

  15. Construct Turing machine for L = {1 n 0 n 1n | n1}

    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 {1n0n | 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.

  16. 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

    1. CFLs are closed under union

      If L1 and L2 are CFLs, then their union L1 + L2 is a CFL.

      Let the grammar CFG1 defines language L1. Assume that the nonterminals in CFG1 are S1, A1, B1, C1…… Let L2 is a language defined by CFG2 and its nonterminals are S2, A2, B2, C2, …..

      Now CFG1 and CFG2 have nonintersecting sets of nonterminals.

      We create a CFG for L1 + L2 as follows:

      Include all of the nonterminals S1, A1, B1, C1, . . . and S2, A2, B2, C2, . . ..

      Include all of the productions from CFG1 and CFG2.

      Create a new nonterminal S and a new production in CFG as

      S→ S1 | S2

    2. CFLs are closed under concatenation

      If L1 and L2 are CFLs, then L1L2 is a CFL.

      Let the grammar CFG1 defines language L1. Assume that the nonterminals in CFG1 are S1, A1, B1, C1 ….. Let L2 is a language defined by CFG2 and its nonterminals are S2, A2, B2, C2, …..

      Now CFG1 and CFG2 have nonintersecting sets of nonterminals.

      We create a CFG for L1L2 as follows:

      Include all of the nonterminals S1, A1, B1, C1, ….. and S2, A2, B2, C2, . . ..

      Include all of the productions from CFG1 and CFG2.

      Create a new nonterminal S and a production

      S → S1S2

    3. 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 S1, 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 → S1S | e

      We can repeat last production

      S → S1S→ S1S1S → S1S1S1S →S1S1S1S1S→ S1S1S1S1e → S1S1S1S1

      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 S1 above generates a word in L. Also, there is no interaction between the different S1’s.

    4. CFLs are not closed under intersection

      Let L1 and L2 are two CFLs. Then L1 ∩ L2 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 L1 = {anbnan: n ≥ 1} is a non context free language. L1 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 L2 be generated by the following CFG:

      S → XY

      X → aXb |ε

      Y → aY |ε

      Thus, L2 = {anbnam: 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 L3 be generated by the following CFG:

      S → WZ

      W → aW |ε

      Z → bZa | e

      Thus, L3 = {aibkak: 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 L2 ∩ L3 = L1, where L1 = {anbnan: n = 0, 1, 2, . . .}, which is a non context free language.

    5. 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 L1 and L2 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.

  17. 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].

    i
    gi
    hi
    1
    100
    1
    2
    0
    100
    3
    1
    00

    Let’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:

    1001100100100
    1001100100100

    Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.

  18. 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.)

  19. 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.

    1. Runs H on input <M, <M>>.
    2. If H accepts it rejects, if H rejects it accepts.
    In summary D(<M>) = image

    When we run D with its own description <D> as input? In that case we get

    D(<D>) = image

    It is forced to do opposite to what D does. Thus neither TM D nor TM H exists.

  20. 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.

    1. 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.
    2. 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.
    3. 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.
  21. 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.

    Δ /Σ
    0
    1
    → q0
    D
    q1
    q1
    D
    q2
    *q2
    q3
    q3
    q3
    q2
    q2
  22. 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, ∑, δ, q0, F}is defined as {w | δ`(q0, w) = P for some P in F}

    Language of NFA A = {Q, ∑, δ, q0, F}is defined as {w | δ`(q0, w) ∩ F ≠ ∅ } i.e there is at least one final state in the resultant

  23. Convert the following NFA to DFA
    δ
    a
    B
    →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.

    δ
    A
    b
    →[p]
    [p]
    [pq]
    [pq]
    [pr]
    [pqr]
    *[pr]
    [p]
    [pq]
    *[pqr]
    [pr]
    [pqr]
  24. Discuss on the relation between DFA and minimal DFA.

    Ans: Let M and M1 be two FA s over . We construct a comparison table consisting of n + 1 columns where n is the no of input symbols.

    1. 1st column consisting of pair of nodes of form (q, q1) where q ∊ M & q1 ∊ M1
    2. If (q, q1) appears in same row of 1st column then corresponding entry in a column (a ∊ ∑) is (qa, qa1) where (qa, qa1) are reachable from q & q1 on a .
    3. Table is constructed by starting with pair of initial vertices qin, qin1 of M & M1 . We complete construction by considering the pairs in 2nd & subsequent column which are not in 1st column.
      1. if we reach a pair (q, q1) such that q is final states of M & q1 is non final state of M1 ⇒ terminate construction and conclude that M & M1 are not equivalent.
      2. if construction is terminated when no new element appears in second & subsequent columns which are not on 1st column. Conclude that M & M1 are equivalent.
  25. 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 R1 & R2 is Regular expression R. (R = R1 + + R2)

      Ex: Let “a” be regular expression R1

      “b” be regular expression R2

      (a + b) is also a regular expression R having the elements {a, b}.

    • Concatenation of two regular expression R1 & R2 written as R1 R2 is also Regular Expression R (R = R1. R2)

      Ex: Let “a” be regular expression R1

      “b” be regular expression R2

      (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.
  26. Discuss in detail about the closure properties of regular languages.

    Ans: The principal closure properties of regular languages are:

    1. The union of two regular languages is regular. If L and M are regular languages, then so is L ∪ M.
    2. The intersection of two regular languages is regular. If L and M are regular languages, then so is L ∩ M.
    3. The compliment of two regular languages is regular. If L is a regular language over alphabet Σ, then Σ*-L is also regular language.
    4. The difference of two regular languages is regular. If L and M are regular languages, then so is L − M.
    5. 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}.
    6. The closure of a regular language is regular. If L is a regular language, then so is L*.
    7. The concatenation of regular languages is regular. If L and M are regular languages, then so is L M.
    8. 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 ”.
    9. 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.
  27. Prove that the following languages are not regular

    (a) {02n / n 1}

    (b) {am bn am + 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 q0, q1 and q2 where q0 is initial state and q2 is final state. Since there exists a finite automaton we can conclude that the given language is Regular.

    (b) {am bv am + n / m ≥ 1 and n ≥ 1 }

    Ans: Let us assume that the language is regular. According to Pumping lemma choose the string Z = ambnam+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, UViW ∈ 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 = ax Such that x ≥ 1.

    Let i = 0, then the string formed is UW, the string would be of the form am−xbnan+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 = bx Such that x ≥ 1.

    Let i = 0, then the string formed is UW, the string would be of the form ambn−xam+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 = axbx Such that x ≥ 1.

    If i = 0, then the string formed is UW, the string would be of the form am−xbn−xam+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 am−xbn−x am+ 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 UV2W, the string would be of the form an−xaxbxaxbxbn−xam+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.

  28. 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 = { Q10, Q20 } Where Q10 is set of final states & Q20 = Q − Q10 is set of non final states.
    • Construct ΠK + 1 from ΠK further partitioning as follows:
      1. Let Q1K be any subset in ΠK . if q1 & q2 are in Q1K they are (K + 1) equivalent provided δ(q1, a) & δ(q2, a) are K – equivalent.
      2. Find out whether δ(q1, a) and δ(q2, a) are in same equivalence class in ΠK for every a Σ. If so, q1 and q2 are (k + 1) equivalence. This way Qi k is further divided into (K + 1) equivalence classes. Repeat this for every Qi 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.
  29. 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
    ⇒ aaabbB
    ⇒ aaabbaBB
    ⇒ aaabbabB
    ⇒ aaabbabbS
    ⇒ aaabbabbbA
    ⇒ aaabbabbba

    The following is a RMD:

    S ⇒aB ⇒ aaBB
    ⇒ aaBaBB
    ⇒ aaBaBbS
    ⇒ aaBaBbbA
    ⇒ aaBaBbba
    ⇒ aaBabbba
    ⇒ aaaBBabbba
    ⇒ aaaBbabbba
    ⇒ aaabbabbba

    (c) Derivation tree/parse tree

  30. Construct PDA for the language L = {wwr | 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 q0 be initial state, qf be final state and Z0 be bottom of the stack.

    δ(q0, a, Z0) = (q0, aZ0)
    δ(q0, b, Z0) = (q0, bZ0)
    δ(q0, a, a) = (q0, aa), (q1, ε)
    δ(q0, b, b) = (q0, bb), (q1, ε)
    δ(q0, a, b) = (q0, ab)
    δ(q0, b, a) = (q0, ba)
    δ(q1, a, a) = (q1, ε)
    δ(q1, b, b) = (q1, ε)
    δ(q1, ε, Z0) = (qf, Z0)

    The final PDA is given by M = {(q0, q1, qf), (a, b), (a, b, Z0), δ, q0, Z0, qf}.

  31. 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, Σ, τ, δ, q0, Z0, ∅} 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 → [q0, Z0, q] for each state q in Q.

    R2:

    For each move that pops a symbol from stack with transition as

    δ (q, a, Z0) = (q1, ε) induces a production as

    [q, Z0, q1] → a for q1 in Q.

    R3:

    For each move that does not pop symbol from stack with transition as δ (q, a, Z0) = (q1, Z1Z2 Z3Z4…..) induces a production as

    [q, Z0, qm] → a[q1, Z1 q2 ] [q2, Z2 q3 ] [q3, Z3 q4 ] [q4, Z4 q5 ]…[qm-1, Zm qm ] for each qm in Q.

    After defining all the rules apply simplification of grammar to get reduced grammar.

  32. 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 → BX1 | bX1 → CD

    The second production after converting to CNF the resultant productions are

    B → YX2 | dX2 → c

    The third production after converting to CNF the resultant productions are

    C → X3A | cX3 → g

    The fourth production after converting to CNF the resultant productions are

    D → X4B| aX4 → d

    And the last is in CNF.

    The final grammar in CNF is

    A → BX1 | b
    X1 → CD
    B → YX2 | d
    X2 → c
    C → X3A| c
    X3 → g
    D → X4B| a
    X4 → d
  33. 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, Σ , Γ, δ, [q0, 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.

    1. { ww | w in Σ*}
    2. { wwR | w in Σ*}
    3. { aibi | i ≥ 1 }
    4. { aibjck| i ≠ j or j ≠k }
    5. { 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.

  34. 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

    1. CFLs are closed under union

      If L1 and L2 are CFLs, then their union L1 + L2 is a CFL.

      Let the grammar CFG1 defines language L1. Assume that the nonterminals in CFG1 are S1, A1, B1, C1…… Let L2 is a language defined by CFG2 and its nonterminals are S2, A2, B2, C2, …..

      Now CFG1 and CFG2 have nonintersecting sets of nonterminals.

      We create a CFG for L1 + L2 as follows:

      Include all of the nonterminals S1, A1, B1, C1, . . . and S2, A2, B2, C2, . . ..

      Include all of the productions from CFG1 and CFG2.

      Create a new nonterminal S and a new production in CFG as

      S→ S1 | S2

    2. CFLs are closed under concatenation

      If L1 and L2 are CFLs, then L1L2 is a CFL.

      Let the grammar CFG1 defines language L1. Assume that the nonterminals in CFG1 are S1, A1, B1, C1 ….. Let L2 is a language defined by CFG2 and its nonterminals are S2, A2, B2, C2, …..

      Now CFG1 and CFG2 have nonintersecting sets of nonterminals.

      We create a CFG for L1L2 as follows:

      Include all of the nonterminals S1, A1, B1, C1, ….. and S2, A2, B2, C2, . . ..

      Include all of the productions from CFG1 and CFG2.

      Create a new nonterminal S and a production

      S → S1S2

    3. 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 S1, 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 → S1S | ε

      We can repeat last production

      S → S1S→ S1S1S → S1S1S1S →S1S1S1S1S→ S1S1S1S1ε → S1S1S1S1

      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 S1 above generates a word in

      L. Also, there is no interaction between the different S1’s.

    4. CFLs are not closed under intersection

      Let L1 and L2 are two CFLs. Then L1 ∩ L2 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 L1 = {anbnan: n ≥ 1} is a non context free language. L1 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 L2 be generated by the following CFG:

      S → XY
      X → aXb |ε
      Y → aY | ε

      Thus, L2 = {anbnam: 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 L3 be generated by the following CFG:

      S → WZ

      W → aW |ε

      Z → bZa | e

      Thus, L3 = {aibkak: 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 L2 ∩ L3 = L1, where L1 = {anbnan: n = 0, 1, 2, . . .}, which is a non context free language.

    5. 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 = 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.

  35. 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

    1. |VX | ≥ 1
    2. |VWX | ≤ n and
    3. For all i ≥ 0 UVi WXi 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 2i-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 ≤ 2i-1. i.e 20 = 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 = 2k, |z| ≥ n then |z| >2k-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 2i-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)

    Thus A bba = w

    i.e path length i = 3

    |w| ≤ 2i-1 i.e 3 ≤ 22

    If we pump s substring into w which satisfies the condition as i ≤ |w| ≤ 2i-1 ≤ n the grammar producing string w is a regular grammar.

  36. 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.)

  37. 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.

    1. Runs H on input <M, <M>>.
    2. If H accepts it rejects, if H rejects it accepts.

    In summary D(<M>) = image

    When we run D with its own description <D> as input? In that case we get

    D(<D>) = image

    It is forced to do opposite to what D does. Thus neither TM D nor TM H exists.

  38. 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 (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].

    i
    gi
    hi
    1
    100
    1
    2
    0
    100
    3
    1
    00

    Let’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:

     

    1001100100100
    1001100100100

    Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.

  39. Describe the following:
    1. Alphabet, String, Language, Empty String.
    2. NFA.
    3. Transition Diagram.
    4. δ in NFA with d (Epsilon) moves

    Ans:

    1. 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) +

    2. NFA:

      Definition 3: Nondeterministic finite automata can be defined as quintuple

      M = (Q, Σ, δ, q0, F)

      Where Q = Non empty finite set of states

      Σ = input alphabet

      q0 = 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 Σ →2Q

    3. Transition Diagram

      A transition graph contains

      1. Set of states as circlesStart state qo with arrow

        Final state by double circle

      2. A finite set of transitions (edges | labels) that show how to go from some state to other.
    4. δ 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.

  40. Write an algorithm to minimize a given FA

    Ans: The minimization algorithm for the given FA based on Π construction is explained here.

    1. Initially construct 0 – equivalence class as Π0 = { Q10, Q20 } Where Q10 is set of final states & Q20 = Q − Q10 is set of non final states.
    2. Construct ΠK + 1 from ΠK further partitioning as follows:
      1. Let Q1K be any subset in ΠK. if q1 & q2 are in Q1K they are (K + 1) equivalent provided δ(q1, a) & δ(q2, a) are K – equivalent.
      2. Find out whether δ(q1, a) and δ(q2, a) are in same equivalence class in ΠK for every a ∈ Σ. If so, q1 and q2 are (k + 1) equivalence. This way Qi k is further divided into (K + 1) equivalence classes. Repeat this for every Qi k in ΠK to get all the elements of ΠK + 1.
    3. Construct Πn for n = 1, 2, 3, … until Πn = Πn + 1.
    4. For required minimum state automation, states are equivalent classes obtained finally.
  41. Minimize the following FA
    S
    0
    1
    →A0
    A0
    A3
    A1
    A2
    A5
    A2
    A3
    A4
    A3
    A0
    A5
    A4
    A0
    A6
    A5
    A1
    A4
    *A6
    A1
    A3

    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.

     

    Π3 (1, 4, 6, 7, 8, 9) = {{A6}, {A4}, {A2, A5}, { A0}, { A1}, {A3}}

     

    Using the new classes we find whether they are 4-equivalent.

    A2
    A5
    0
    9
    8
    1
    4
    4

    From 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.

  42. 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.

  43. 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.

  44. Construct the Left Linear Grammar for the following Regular Expressions:
    1. (11 + 0)* (00 + 1)*
    2. 10 + (0 + 11)0*1

      Ans: for the regular expression the left linear grammar is as follows.

    1. (11 + 0)* (00 + 1)*

      Corresponding Left Linear grammar is

      S→ A00 | A1 | ε,

      A→ A00 | A1 | B,

      B→ B11 | B0 | ε

    2. 10 + (0 + 11)0*1

      Corresponding Left Linear grammar is

      S→ 10 | A1

      A→ B0 |C

      B → 11 | 0

  45. Design DPDA for the language L = { an b2n / 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 = ({q0, q1, q2}, {a, b}, {a, Z0}, δ, q0, Z0, {qf}), where δ is defined by following rules:

    δ(q0, a, Z0) = {(q0, aZ0)}
    δ(q0, a, a) = {(q0, aa)}
    δ(q0, b, a) = {(q1, a)}
    δ(q1, b, a) = {(q2, ε)}
    δ(q2, b, a) = {(q1, a)}
    δ(q2, ε, Z0) = {(qf, Z0)}

    To show that aabbbb is accepted by the PDA ID’s of the system while processing the string are as follows.

    (q0, aabbbb, Z0) ⇒ (q0, abbbb, aZ0) ⇒ (q0, bbbb, aaZ0) ⇒(q2, bb, aZ0) ⇒ (q1, b, aZ0) ε, Z0) ⇒ (qf, ε, Z0)

  46. 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.)

  47. 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 (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

    i
    gi
    hi
    1
    100
    1
    2
    0
    100
    3
    1
    00

    Let’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:

     

    1001100100100
    1001100100100

    Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.

  48. Design Turing Machine over Σ_ = {1} to accept the language L = {1m / m is odd}
  49. 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, Σ, γ, δ, q0, B, F). Its transition function is a partial function

     

    δ :QX(Г∪ {B})n → (Q{h})X(Г∪{B})nX{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.
  50. Explain the steps in conversion of NFA to DEA convert the following NFA to DFA.

    Ans:

    Q = 23 = 8 states = all subsets of q0, q1, q2

    = {∅, [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2]}

    Σ = 0, 1

    q0 = [q0]

    F = {[q2], [q0, q2], [q1, q2], [q0, q1, q2]}

    δ is given by δD ([q1 q2], a) = δ n (q1, a) U δn (q2, a)

    when δn is transition function NFA.

    0
    1
    [q0]
    [q0, q1]
    [q0]
    [q1]
    [q2]
    [q2]
    [q0, q1]
    [q0, q1]
    [q0, q2]
    *[q0, q2]
    [q0, q1]
    [q0]
    [q1, q2]
    [q2]
    [q0, q1, q2]
    [q0, q1]
    [q0, q2]

    The states [∅], [q1], [q2], [q1, q2] and [q0, q1, q2] 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

    1. Start with initial state. Do not add all subsets of states as there may be unnecessary states.
    2. 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 δ(q0, a) = {q0, q1} say then add this as new state in DFA. and find transition from this state on input symbol.
    3. Declare the states as final if it has at least one final state of NFA.
  51. 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 (q0) = {q0, q1, q2}

    ε-closure (q1) = {q1, q2}

    ε-closure (q2) = {q2}

    Step 2: Find the transition on each state for each element.

    (q0, 0) = ε-closure (δ(ε-closure (q0), 0))
    = ε-closure (δ({q0, q1, q2}, 0))
    = ε-closure ({q0}, ∪{Ø}, ∪{Ø})
    = {q0, q1, q2}

     

    (q0, 1) = ε-closure (δ(ε-closure (q0), 1))
    = ε-closure (δ({q0, q1, q2}, 1))
    = ε-closure ({Ø}, ∪{q1}, ∪{Ø})
    = {q1, q2}

     

    (q0, 2) = ε-closure (δ(ε-closure (q0), 2))
    = ε-closure (δ({q0, q1, q2}, 2))
    = ε-closure ({Ø}, ∪{Ø}, ∪{q2})
    = {q2}

     

    (q1, 0) = ε-closure (δ(ε-closure (q1), 0))
    = ε-closure (δ({q1, q2}, 0))
    = ε-closure ({Ø})
    = {Ø}

     

    (q1, 1) = ε-closure (δ(ε-closure (q1), 1))
    = ε-closure (δ({q1, q2}, 1))
    = ε-closure ({q1}, ∪{Ø})
    = {q1, q2}

     

    (q1, 2) = ε-closure (δ(ε-closure (q1), 2))
    = ε-closure (δ({q1, q2}, 2))
    = ε-closure ({Ø}, ∪{q2})
    = {q2}

     

    (q2, 0) = ε-closure (δ(ε-closure (q2), 0))
    = ε-closure (δ({q2}, 0))
    = ε-closure ({Ø})
    = {Ø}

     

    (q2, 1) = ε-closure (δ(ε-closure (q2), 1))
    = ε-closure (δ({q2}, 1))
    = ε-closure ({Ø})
    = {Ø}

     

    (q2, 2) = ε-closure (δ(ε-closure (q2), 2))
    = ε-closure (δ({q2}, 2))
    = ε-closure ({q2})
    = {q2}

    NFA without – ε transitions is

    Transition diagram of NFA without ε-transitions

  52. Prove the equivalence of NFA and DFA using subset construction.

    Ans:Let MN = (QN, ΣN, δn, qON, FN) be given NFA to construct equivalent DFA MD define MD as follows.

    1. QD = 2QN. If NFA has n states. DFA at most can have 2n states.
    2. Σn = ΣD
    3. [q0] = {qo}
    4. FD = Set of all states of QD that contains at least one final states of FN.
    5. δD ((q1, q2, q3), a)    = δn(q1, a) ∪ δn (q2, a) ∪ δn(q3, a)
      = {P1, P2, P3} say

      Add state [ P1, P2, P3] to QD if it is not there.

  53. Give Deterministic finite automata accepting the following language over the alphapet.
    1. 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.

    2. Number of 1’s is not a multiples of 3
  54. 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)

  55. Discuss the closure properties of regular languages.

    Ans: The principal closure properties of regular languages are:

    1. The union of two regular languages is regular. If L and M are regular languages, then so is L ∪ M.
    2. The intersection of two regular languages is regular. If L and M are regular languages, then so is L ∩ M.
    3. The compliment of two regular languages is regular. If L is a regular language over alphabet Σ, then Σ*-L is also regular language.
    4. The difference of two regular languages is regular. If L and M are regular languages, then so is L − M.
    5. 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}.
    6. The closure of a regular language is regular. If L is a regular language, then so is L*.
    7. The concatenation of regular languages is regular.If L and M are regular languages, then so is L M.
    8. 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 ”.
    9. 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”.
  56. 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.

  57. Using pumping lemma for regular sets prove that the language

     

    L = {0m1n0m-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 = 0m 1n 0m + 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, UViW ∈ 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 = 0x Such that x ≥ 1.

    Let i = = 0, then the string formed is UW, the string would be of the form 0m-x 1n 0m + 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 = 1x Such that x ≥ 1.

    Let i = 0, then the string formed is UW, the string would be of the form 0m 1n-x 0m + 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 = 0x1x Such that x ≥ 1.

    If i = 0, then the string formed is UW, the string would be of the form 0m-x 1n-x 0m + 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.

  58. Convert the following grammar into GNF.

    S XY1/0

    X 00X/Y

    Y1X1

    Ans: Step 1: Since there are unit productions first eliminate it and the resulting grammar is

    S → XY1/0
    X → 00X/1X1
    Y → 1X1

    Step 2: Converting the grammar to CNF we get

    S → XP/0
    P → YB
    X → AQ/BR
    Q → AX
    R → XB
    Y → BR
    A→ 0
    B → 1

    Step 3: Converting the grammar to GNF we get

    S → 0QP | 1RP |0
    P → 1RB
    X → 0Q/1R
    Q → 0X
    R → 0QB | 1RB
    Y → 1R
    A → 0
    B → 1
  59. Give formal pushdown automata that accepts {wcwR | 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 q0 be initial state, qf be final state and Z0 be bottom of the stack.

    δ(q0, 0, Z0) = (q0, 0Z0)
    δ(q0, 0, 0) = (q0, 00)
    δ(q0, 0, 1) = (q0, 01)
    δ(q0, 1, Z0) = (q0, 1Z0)
    δ(q0, 1, 0) = (q0, 10)
    δ(q0, 1, 1) = (q0, 11)
    δ(q0, c, Z0) = (q1, Z0)
    δ(q0, c, 0) = (q1, 0)
    δ(q0, c, 1) = (q1, 1)
    δ(q1, 0, 0) = (q1, ε)
    δ(q1, 1, 1) = (q1, ε)
    δ(q1, ε, Z0) = (qf , Z0)

    The final PDA is given by M = {(q0, q1, qf), (a, b, c), (a, b, Z0), δ, q0, Z0, {qf}}.

  60. Show that the following grammars are ambiguous.

    {S aSbS / bSaS / ε} and

    Ans: The string abab can be derived using LMD as follows

    1. S = > aSbS = >abS = > abaSbS = > ababS = > abab
    2. 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, Bb}

    Ans: The string aab can be derived using LMD as follows

    1. S = > AB = >AaB = > aaB = > aab
    2. 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, ε, α)

  61. 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 0m. 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 m10 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 B02103B. After processing the tape content would be B05B. 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 B05B. Sequence of steps is given for understanding.

    1. In initial state 0’s is replaced by B and change to new state.

      δ(q0, 0) = (q1, B, R)

    2. 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

  62. 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

    1. There is a production X → ε
    2. There is a derivation that starts at X and leads to ε:

      X = > . . . = >ε i.e., Xε

    For any language L, define the language L0 as follows:

    1. if ε ∉L, then L0 is the entire language L, i.e., L0 = L.
    2. if ε ∈ L, then L0 is the language L - {ε}, so L0 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 L0.

    Procedure for eliminating ε productions:

    1. Construct Vn set of all nullable variables
    2. For each production B → A, if A is nullable variable, replace nullable variable by ε and add with all possible combinations on the RHS.
    3. Do not add the production A → ε
  63. Write short notes on the following:
    1. 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 A0. 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 A0 are placed on the upper track and the contents of the tape to the left of A0 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 A0 the moves are implemented as they are reading symbols from upper track. If the reading head is to the left of A0 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.

    2. 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.

      1. Let us place the given number on first track in binary form bounded by Φ and $. For example 47 is represented as Φ101111$.
      2. On the second track write 2 in binary form as 10.W
      3. Copy the number on first track to third track.
      4. 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.
      5. 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.
      6. If the number on third track in nonzero and increase number on second track by one.
      7. Repeat the steps 4-6 until the number on second is equal to number on first.
  64. 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.

    1. 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.
    2. 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.
    3. 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.
  65. 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 languages
    Recursively enumerable languages

    1. 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 (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 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].

    i
    gi
    hi
    1
    100
    1
    2
    0
    100
    3
    1
    00

    Let’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:

    1001100100100
    1001100100100

    Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP problem.

  66. 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 (δ)

    1. δ (q, ε) = q

      This means the state of the system can be changed only by an input symbol else remains in original state.

    2. For all strings w and input symbol a

      δ(q, aw) = δ(δ(q, a), w)

      similarly δ(q, wa) = δ(δ(q, w), a)

    3. 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 δ(q0, x) = P for some P in F.

    Method: A finite automata accepts a string w = a1 a2 an 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 a1 a2 an

    • The Language accepted by finite automata (A) is

      L(A)={w :images(q0,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 :images( q0 ,w)∩F≠ɸ}

    Transition function and language of ε–NFA

    The transition function is defined as:

    1. (q, ε) = ε – CLOSURE(q)
    2. For w in Σ*, and a in Σ

      (q, wa) = ε-CLOSURE(P)

      Where P = {p │ for some r in images(q,w), p in δ(r,a)}

    3. (R,a)=δ(q,a)
    4. (R,w)=(q,w)

    The language accepted by NFA with ε – move is defined as:

    L (M)={w | images(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.

  67. 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)

     

  68. Consider the alphabet A = {a, b} and the language L = {bb, bab, baab, baaab,……} over A.
    1. Is A* finite or infinite? Give a brief reason for your answer.        (2)
    2. Write down a regular expression that represents the above language L.        (4)
    3. Write down a regular grammar which describes the above language L.        (4)
    4. Draw the DFA corresponding to the above language L.         (6)

    Ans: Given:

    A = {a, b}

    L = {bb, bab, baab, baaab, …..}

    Solution:

    1. A* is infinite, since it is a combination of all possible a’s and b’s including ·

      A* = {ε, a, b, aa, bb, ab, ba, ….}

    2. RE = ba*b
    3. Regular grammar

      S → bS1

      S → b│aS1

    4.  

  69. Find an equalities for the following regular expression and prove for the same.
    1. b + ab* + aa*b + aa*ab*
    2. a*(b + ab*)
    3. a(a + b)* + aa(a + b)* + aaa(a + b)*        (9)
    1. Ans: (1) b + ab* + aa*b + aa*ab*

      = (b + ab*) + aa*(b + ab*)

      = (ε + aa*) (b + ab*)

    2. a*(b + ab*)

      = a*b + a*ab* = a* b + a + b*

    3. a (a + b)* + aa (a + b)* + aaa(a + b)*

      = (a + aa + aaa) (a + b)*

  70. 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 L1 and L2 be regular sets such that

    L1 = T(A1) and L2 = T(A2) where

    A1 = (Q1, Σ1, δ1, q1, F1 ) and A2 = (Q2, Σ2, δ2, q2, F2)

    We shall assume that Q1 ∩ Q2 = ɸ

    1. Union: Let A = (Q, Σ, δ, q0, F), where

      Q = Q1 ∪ Q2 ∪ {q0 }, q0 E Q1 ∪ Q2

      q0 is the start date, Σ = Σ1 ∪ Σ2, F = F1 ∪ F2 and δ· is defined as follows:

      δ(q0, λ) = {q1, q2}

      If q ∈ δ1(p, a) then q ∈ δ(p, a)

      If q ∈ δ2 (p, a) then q ∈ δ(p, a)

      It is clear that T(A) = (L1 ∪ L2)

    2. Concatenation: Let A = (Q, Σ, δ, q0, F ) where

      Q = Q1 ∪ Q2, Σ = Σ1 ∪ S2, q0 = q1, F = F2 and

      δ is defined as follows:

      δ (q, a) = {δ1(q, a)} for each q in Q1 − F1

      δ (q, a) = {δ2(q, a)} for each q in F1

      and δ (q, a) = {δ2(q, a)} for each q in Q1

      A word w is in L1, L2 if w = w1 w2 where w1 ∈ L1and w2 ∈ L2. This is equivalent to δ1(q1, w) being in F1 which is equivalent to w1 w2 being in T(A). Thus L1 L2 = T(A).

    3. Closure: Let L = T(A)be a regular set where

      A = (Q, Σ, δ, q0, F)

      Let        B = (Q, Σ, δ′, q0, F),

      Where δ′ is defined as follows:

      δ′ (q, a) = {δ(q, a)} if q is in Q − F and

      δ′ (q, a) = {δ(q, a), δ(q0, 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 λ.

    4. 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, δ, q0, 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, Σ, δ, q0, Q − F).

      The M′accepts a word w if and only if δ(q0, 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.

    5. Theorem

      If X and Y are regular sets over Σ, then XY is also regular.

      Proof

      XY = XY 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.

    6. Therorem

      If L is regular then LR is also regular.

      Proof

      As L is regular, we can construct aFA

      M = (Q, Σ1, δ, q0, 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 q0 defined as the (only)

      final state of M′ (i.e.) M′ = (Q, Σ1, δ, F, {q0}).

      If w T(M), we have a path from q0, 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 q0. Its path value is wR. So wR ∈ T(M). In a similar way, we can see that if w1 ∈ T(M’), then w1R ∈ 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 wR ∈ T(M′) by induction on │w│. Since T(M′) is regular it follows that T(M)R is regular.

    7. 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.

    8. 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, Σ, δ, q0, 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,Δ, δ′, q0, 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 δ′(q0, x) = δ(q0, h(x)). Therefore M′ accepts x if and only if M accepts h(x). That is L(M) = h-1L(M).

  71. 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, Σ,δ, q0, F) with reduced number of states.

    Steps

    • Mark the pair of inequivalent states (p, q) with ‘X’
      1. Initially ‘X’ is placed by considering one final state and one non-final state, where δ(p, x) ∈ F and δ(q, x) ∈ F.
      2. 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:

    States
    Inputs
    a
    b

    →q0

    q0
    q0

    *q1

    q1
    q1

    In this representation q0 is the start date and q1 is the final state. Therefore it can’t be reduced further.

    Given w = baaab

    δ(q0, baaab)

    = δ(δ(q0, b), aaab)

    = δ(q1, aaab)

    = δ(δ(q1, a), aab)

    = δ(q1, aab)

    = δ(δ(q1, a), ab)

    = δ(q1, ab)

    = δ(δ(q1, a), b)

    = δ(q1, b)

    = q1 ∈ F

    String is accepted

  72. Consider the grammar:
    1. S I C t S
    2. S I C t S e S
    3. S a
    4. C b

    where I, t, and, e stand for if, then, and else, and C and S for “conditional” and “statement” respectively.

    1. Construct a leftmost derivation for the sentence w = i b t i b t a e a.
    2. Show the corresponding parse tree for the above sentence.
    3. Is the above grammar ambiguous? If so, prove it.
    4. Remove ambiguity if any and prove that both the grammar produces the same language.        (16)

    Ans:

    1. 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)

    2.  

    3. 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.

  73. Consider the GNF CFG G = ({S, T, C, D}, {a, b, c, d}, S, P) where P is:
    S→ cCDdTC│∈     C→a T D c
    T→ cDCcSTa     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, Σ, Γ, δ, q0, z0,ɸ )

    where:

    Q = {q0, q1, q2}

    Σ = {a, b, c, d}

    Γ = {S, T, C, D, z0}

    δ is defined as:

    δ(q0, λ, z0) = {(q1, Sz0)}

    δ(q1, λ, S) = {(q1, cCD), (q1, dTC), (q1, ε)}

    δ(q1, λ, T) = {(q1, cCD), (q1, cST), (q1, a)}

    δ(q1, λ, C) = {(q1, aTD), (q1, c)}

    δ(q1, λ, D) = {(q1, dC) (q1, d)}

    δ(q1, a, a) = {(q1, λ)}

    δ(q1, b, b) = {(q1, λ)}

    δ(q1, c, c) = {(q1, λ)}

    δ(q1, λ, z0) = {(q2, λ)}

  74. Define Pumping Lemma for Context Free Languages. Show that L = {ai bj ck: i < j < k} is not context-free.        (6)

    Ans: Let n be the pumping –lemma constant and consider string z = anb(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 uv3wx3y 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.

  75. Construct a Turing MachineTM 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:

    δ(q0, λ) = (q1, λ, R)

    δ(q1, a) = (q2, λ, R)

    δ(q2, a) = (q2, a, R)

    δ(q2, λ) = (q3, a, R) where q3 ∈ F

  76. Convert the following grammar into an equivalent one with no unit productions and no useless symbols. Convert to Chomsky Normal Form (CNF).        (16)

    S ACB

    A CD

    B 1B1

    C 0C0

    D 2D2

    Ans: Given

    S→A│CB

    A→C│D

    B→1B│1

    C→0C│0

    D→2D│2

    Solution:

    1. 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 

      C → 0C│0

      D → 2D│2

    2. Let G1 = (N1, {0, 1, 2}, S, P1) where P1 is:

      S → 0│2│CB

      B → 1        C → 0        D → 2 are added to P1

      S → 0C│2D,        B → 1B        C → 0C

      D → 2D yield

      S → A1C│A3D,        B → A2B,        C → A1C

      D → A3D,        WHERE A1 → 0,        A2 → 1,        A2 → 2

      ∴ N1 = {S1 A1, A2, A3, B, C, D}

      Here G1 is in CNF for the given grammar

  77. 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.

  78. 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.

  79. 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.

  80. 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 {x1, x2, …} 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.

  81. 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, Σ, δ, q0, F1) be an NFA with ε-transitions. Construct M1 which is NFA without ε-transitions.

    M1 =(Q, S, δ1, q0, F ) where
    F1=F {q0 } if ε-CLOSURE (q0 ) contain a state of F.

    Let x be any string

    δ1(q0 , x)=δ(q0 ,x)

    This statement is not ture if x = ε because δ1( q0,ε )={q0} and

    (q0,ε) = ε-CLOSURE(q0)

    Basic step

    | x | = 1 x is a symbol whose value is

    δ1(q0,a)=δ(q0,a) (because by definition of )

    Induction step

    let  x =wa where a  is in Σ

    δ1(q0,wa )=δ11 (q0 ,w ),a )

    1(δ(q0,w),a)

    = (p,a)[because by induction hypothesis

    δ(q0,w)= (q0,w)=p(say)]

    Now we must show that

    δ1(p,a)=δ(q0,wa)

    But

    δ1(p,a)=δ1(q,a)=δ(q,a)
    = δ(δ1(q0,w),a)
    = δ(q0,wa)
    = (q0,x)
    Hence δ1(q0,x) = (q0,x)
  82. Construct an NFA without ε - transitions for the following NFS.        (8)

    Ans: NFA with ε-transition table (M):

    NFA without ε-transition table (M1):

    The set of final states of M1=F∪{q0}={q0,q2}since ε-CLOSURE{q0}={q0,q1,q2}

    Transaction diagram:

  83. 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:

    1. r = ε
    2. r = ɸ
    3. 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 = r1 + r2. Both r1 and r2 must have fewer that i operators. Thus there are NFA’s M1 = (Q1, ∑1, δ1, q1, { f1}) and M2 = (Q2, ∑2, δ2, q2, { f2}) with L(M1) = L(r1) and L(M2) = L(r2). Assume Q1 and Q2 are disjoint.

    Let q0, f0 be a new initial and final state respectively.

    ∴ M = (Q1∪ Q2∪ {q0, f1}, ∑1∪∑2, δ, q0, { f0}) where δ is defined by

    1. δ(q0, ε) = {q1, q2}
    2. δ(q, a) = δ1 (q, a) if q∈Q1−{ f1}, a∈∑1∪{ε}
    3. δ(q, a) = δ2 (q, a) if q∈Q2−{ f2}, a∈∑2∪{ε}
    4. δ1( f1, ε) = δ2 ( f2, ε) = { f0}

    All the moves of M1 and M2 are present in M. Any path in the transition diagram of M from q0 to f0 must being by going to either q1 or q2 on ε. If the path goes to q1, it may follow any path in M1 to f1 and then goto f0 on ε.

    Similarly paths that begin by going to q2, may follow any path in M2 to f2 and then go to f0 on ε. These are the only paths from q0 to f0. That is, there is a path labeled x in M1 from q1 to f1 or a path in M2 from q2 to f2. Hence L(M) = L(M1) ∪ L(M2)

    Case 2:

    Let r = r1 r2. Let M1 and M2 be as in case 1. Construct M = (Q1 ∪ Q2, ∑1 ∪ ∑2, δ, {q1}, { f2}), where δ is given by

    1. δ(q, a) = δ1(q, a) for q in Q1−{ f1} and a in ∑1 ∪ {ε}
    2. δ( f1, ε) = {q2}
    3. δ(q, a) = δ2(q, a) for q in Q2 a in ∑2∪{ε}

    Every path in M from q1 to f2 is a path labeled by some string x from q1 to f1, followed by the edge from f1 to q2 labeled ε, followed by a path labeled by some string y from q2 to f2.

    Thus L(M) = {xy|x is in L(M1) and y is in L(M2)} and L(M) = L(M1).L(M2).

    Case 3:

    Let r = r1*. Let M1 = (Q1, ∑1, δ1, q1, { f1}) and L(M1) = r1. Construct M = (Q1∪ {q0, f0}, ∑1, δ, q0, { f0}), where δ is given by

    δ(q0, ε) = δ( f1, ε) = {q1, f0}

    δ(q, a) = δ1(q, a) for q in Q1−{ f1} and a in ∑1∪{ε}

    Any path from q0 to f0 consists either of a path from q0 to f0 on ε or a path from q0, to q1 on ε followed by some number of paths from q1 to f1, then back to q1 on ε. There is a path in M from q0 to f0 labeled x if and only if we write x = x1x2……xj fro some j ≥ 0 such that each xi∈L(M1). Hence L(M) = L(M1)*

  84. Find the regular expression corresponding to the following automata.         (8)

    Ans: We will find Rij(0) where K = 0

    R11(0) = ε

    because from state q1 to q1 can be achieved only by ε transition.

    R12(0) = 0

    because from q1 we can reach q2 by ‘0’ input.

    R13(0) = 1

    because from q1 we can reach q3 by ‘1’ input δ(q1, 1) = q3

    R21(0) = 0

    because δ(q2, 0) = q1

    R22(0) = ε

    because from q2 we can reach q2 only on ε transition

    R23(0) = 1

    because δ(q2, 1) = q3

    R31(0) = ɸ

    because from q3 to reach q1 no such path exists

    R32(0) = 0 + 1

    because from q3 to reach q2 we can give either ‘0’ or ‘1’ as input symbol.

    R33(0) = ε

    to remain in q3 it needs ε transition.

    Tabulation is as follows for K = 0:

    R11(0)
    ε
    R12(0)
    0
    R13(0)
    1
    R21(0)
    0
    R22(0)
    ε
    R23(0)
    1
    R31(0)
    ɸ
    R32(0)
    0 + 1
    R33(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 {q1, q2, q3})

    Rij(K) = Rij(K1) + RiK(K1)(RKK(K1))*RKj(K1)

    Therefore for K = 1

    R11(1) = R11(0) + R11(0)(R11(0))* R11(0)

    = ε + ε(ε)*ε
    = ε

    R12(1) = R12(0) + R11(0)(R11(0))* R12(0)

    = 0 + ε(ε)*0
    = 0 + 0 = 0

    R13(1) = R13(0) + R11(0)(R11(0))* R13(0)

    = 1 + ε(ε)*1
    = 1 + 1 = 1

    R21(1) = R21(0) + R21(0)(R11(0))* R13(0)

    = 0 + 0(ε)*ε
    = 0 + 0 = 0

    R22(1) = R22(0) + R21(0)(R11(0))* R12(0)

    = ε + 0(ε)*0
    = ε + 00

    R23(1) = R23(0) + R21(0)(R11(0))* R13(0)

    = 1 + 0(ε)*1
    = 1 + 01

    R31(1) = R31(0) + R31(0)(R11(0))* R11(0)

    = ɸ + ɸ(ε)*ε
    = ɸ + ɸ
    = ɸ

    R32(1) = R32(0) + R31(0)(R11(0))* R12(0)

    = 0 + 1 + ɸ(ε)*)
    = 0 + 1 + ɸ
    = 0 + 1

    R33(1) = R33(0) + R31(0)(R11(0))* R13(0)

    = ε + ɸ(ε)*1
    = ε

    Tabulation is as follows for K = 0:

    R11(1)
    ε
    R12(1)
    0
    R13(1)
    1
    R21(1)
    0
    R22(1)
    ε + 00
    R23(1)
    1 + 01
    R31(1)
    ɸ
    R32(1)
    0 + 1
    R33(1)
    ε

    Now for K = 2

    Rij(1) = Rij(21) + Ri2(21)(R22(21))* R2i(21)

    = Rij(1) + Ri2(1)(R22(1))* R2i(1)

    Therefore

    R11(2) = R11(1) + R12(1)(R22(1))* R21(1) = ε + 0(ε + 00)*0

    = ε + 0(00)*0 = (00)*

    R12(2) = R12(1) + R12(1)(R22(1))* R22(1) = 0 + 0(ε + 00)*(ε + 00)

    = 0 + 0(00)* = 0(00*) (∴R + RS* = RS*)

    R13(2) = R13(1) + R12(1)(R22(1))* R23(1) = 1 + 0(ε + 00)*(1 + 01)

    Here (ε + 00)* = (00)*

    and (1 + 01) = (ε + 0)1

    and so R13(2) = 1 + 0(00)*(ε + 0)1

    Here (00)*(ε + 0) = 0*

    Hence 0(00)*(ε + 0)1 = 0(0*)1

    ∴ R13(2) = 1 + 00*1 = 0*1

    R21(2) = R21(1) + R21(1)(R12(1))* R21(1)

    = 0 + (ε + 00)(ε + 00)*0
    = 0 + 00(00)*0
    = 0(00)*

    R22(2) = R22(1) + R22(1)(R22(1))* R22(1)

    = (ε + 00) + (ε + 00)(ε + 00)*(ε + 00)
    = (00)*

    R23(2) = R23(1) + R22(1)(R22(1))* R23(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*1

    R31(2) = R31(1) + R32(1)(R22(1))* R21(1)

    = ɸ + (0 + 1)(ε + 00)*0
    = ɸ + (0 + 1)(00)*0
    = (0 + 1)(00)*0 (because (ε + 00)* = (00)*)

    R32(2) = R32(1) + R32(1)(R22(1))* R22(1)

    = (0 + 1) + (0 + 1)(ε + 00)*(ε + 00)
    = (0 + 1) + (0 + 1)(00)*
    = (0 + 1)(00)* (because R + RS* = RS*)

    R33(2) = R33(1) + R32(1)(R22(1))* R23(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*1

    Tabulation is as follows for K = 0:

    R11(2)
    (00)*
    R12(2)
    0(00)*
    R13(2)
    0*1
    R21(2)
    0(00)*
    R22(2)
    (00)*
    R23(2)
    0*1
    R31(2)
    (0 + 1)(00)*0
    R32(2)
    (0 + 1)(00)*
    R33(2)
    ε + (0 + 1)0*1

    No we will find regular expression L(M)

    L(M) = R1j(n)

    i.e., R1j1(n) + R1j2(n) + …. + R1jp(n)

    Where F is set of final sets

    F = {qj1, qj2, … qjp}

    In our example, the set of final states

    F = {q2, q3}

    ∴ L(M)= R12(3) +R13(3) (where n =3 states)

    ∴R12(3) = R12(2) +R13(2)(R33(2))*R32(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*)

    R13(3) =R13(2) +R13(2)(R33(2))*R33(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*)

    Hence regular expression is

    R12(3) = R13(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)*

  85. 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 = {q0, q1, qf} = set of states

    ∑ = terminals of grammar G

    ϒ = V∪{z} where V is the variables in grammar G

    F = {qf} = final state.

    The transition function will include

    δ(q0, λ, z) = {q1, 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

    1. δ(q1, λ, A) = {(q, α)} for each A→α in P
    2. δ(q, a, a) = {(q, λ)} for each a∈∑
  86. Construct a PDA equivalent to the following grammar.

    S→ aAA A → aS | bS |a        (7)

    Ans: SaAA

    AaS|bS|a

    The PDA equivalent of the given grammar is:

    M = ({q}, (a, b), {S, a, b, A}, δ, q, S, ɸ) where δ is defined as:

    R1: δ(q,λ,S ) = {(q,aAA )}

    R2 : δ (q,λ,A ) = {(q,aS),(q,bS),(q,a)}

    R3 : δ(q,a,a) = {(q,λ)}

    R4 : δ(q,b,b) = {(q,λ)}

    Test whether some string abaaaa is in N(M).

    (q, abaaaa, S ) (q, a baaaa, aAA) by R1

    (q, baaaa, AA) by R1
    (q, baaaa, bSA) by R2
    (q, aaaa, SA) by R4
    (q, aaaa, aAAA) by R1
    (q, aaa, AAA) by R3
    (q, aaa, aAA) by R2
    (q, aa, AA) by R3
    (q, aa, aA) by R2
    (q, a, A) by R1
    (q, a, a) by R2
    (q, l, l) by R3
  87. 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

    1. It has single final state qf iff the stack is empty.
    2. All transitions must have the form

      δ(qi, a, A) = {C1, C2…..Cn}, where

      δ(qi, a, A) = (qj, λ)        (1)

      δ(qi, a, A) = (qj, BC)        (2)

    That is, each move either increases or decreases the stack content by a single symbol.

    Given M = (Q, ∑, ϒ, δ, q0, z0, {qf}) 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 → [q0, z0, q] for each q in Q.

    P consist of: u, v∈∑*

    A, X ∈ ϒ*, qi, qjQ

    (qi, uv, AX)(qj, v, X)

    Implies that (qi, A, qj)→u

    Consider [qi, A, qk]→a[qj, B, qi] [qi, C, qk]

    The corresponding transition for PDA is

    δ(qi, a, A) = {(qj, B C)……}

    Similarly if [qi, A, q, ] →a then the corresponding transition is δ(qi, a, A) = {(qj, λ)} For all sentential forms leading to a terminal string, the argument holds true.

    The conclusion is

    (q0, w,z0 ) | − * (qj , λ, λ) is true iff (q0z0qf)w

    Consequently L(M) = L(G)

  88. Construct a PDA for the set of palindrome over the alphabet {a, b}.        (8)

    Ans:

    M = (Q,Σ,Г,d,q0,z, F) where

    Q = {q0,q1,q2}

    Σ = {a,b}

    Г = {z,a,b}

    F = {q2}

    The transition function has several parts :

    1. set to push w on to stack.

      δ(q0,a,a) = {(q0,aa)}→(1)

      δ(q0,b,a) = {(q0,ba)}→(2)

      δ(q0,a,b) = {(q0,ab)}→(3)

      δ(q0,b,b) = {(q0,bb)}→(4)

      δ(q0,a,z) = {(q0,az)}→(5)

      δ(q0,b,z) = {(q0,bz)}→(6)

    2. To find middle of the string, where npda switches from q0 to state q1.

      δ(q0,λ,a) = {(q1,a)}→(7)

      δ(q0,a,b) = {(q1,b)}→(8)

    3. Set to match wR against contents of the stack.

      δ(q1,a,a) = {(q1,λ)}→(9)

      δ(q1,b,b) = {(q1,λ)}→(10)

      and finally

      δ(q1,λ,z) = {(q2,z)}→(11)

      To recognize successful match.

      The processing of string w = abba

      ( q0,abba, z )|−( q0,bba,az ) → by rule 5

      |−( q0,ba,baz ) → by rule 2
      |−( q1,ba,baz ) → by rule 8
      |−( q1,ba,baz ) → by rule 8
      |−( q1,a,az ) → by rule 10
      |−( q1,a,az ) → by rule 9
      |−( q1,λ,z ) → by rule 9
      |−( q2,λ ) → by rule 11

    Hence string is accepted.

    Note:

    At 3rd move, to locate middle of the string, (q0, bc, baz) we have two choices for next move

    1. δ(q0, b, b) = {(q0, bb)} (or)
    2. δ(q0, λ, b) = {(q1, b)}
  89. 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 G1, such that each variable in G1 derives some terminal string.

    Proof:

    Let G = (N, T, S, P) and G1 = (N1, T1, S, P1)

    1. Construction of N1

      We define W1 ⊆ N by recursion. W1 = {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) = ɸ).

      Wi + 1 = Wi∪{A∈N| there exists some production A→α with α∈ (T∪Wi)*}

    2. 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.

      1. If each A ∈ Ni than A w for sme w ∈ T*; conversely, if A w then A∈Ni
      2. L(Gi) = L(G)

      To prove (i) we note that Wk + 1 W2 ∪ ∪ Wk.. We prove by induction on i

    That for i = 1, 2, … k, A ∈ Wi implies A w for some w ∈ T*. If A∈W1, then A w.So the production w is in P1.Therefore, A w. Thus there is basis for induction.

    *Let us assume the result for i. Let A∈Wi + 1. Then either A ∈ wi, in which case, A w for some w∈T* by induction hypothesis. Or, there exists a production A→α is P1. e can write α = X1 X2….Xm, where Xj∈T∪Wi. If Xj∈Wi by induction hypothesis, Xj G Wj for some Wj ∈Xj). 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(G1) ⊆ L(G) as N1 ⊆ N and P1 ⊆ P.

    To prove L(G)⊆L(G1), 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∈W1⊆N1. As A∈N1 and w∈T*, A→w is in P1. 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 X1 X2….Xm A w1w2….wm such that Xj wj. If Xj∈T then wj = xj → 2

    If Xj∈N then by equation 1 above, Xj∈N1. As Xj wj is atmost k steps, Xj Also, X1, X2, ……Xm ∈(T∪N1)* implies A→X1, X2, …Xm is in P1. Thus A X1, X2 …..Xm w1w2….wm. Hence by induction, equation 1 is true for all derivations. In particular, S w implies S w. This prove that L(G)⊆L(G1), and equation 2 is completely proved.

  90. 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)

    Proof

    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 = (N1, T, S, P1) where P1 and N1 are constructed as follows:

    1. All the productions in P of the form A→a or A→BC are included in P1, All the variables in N are included in N1.
    2. Consider A→X1, X2…..Xn with some terminal on R.H.S. If Xi is a terminal, say ai, add a new variable Cai to N1 and Caiai to P1. In production A→X1 X2….Xn, 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 P1. Thus we get G1 = (N1, T, P1, S).

    Step 3: Restricting the number of variables on R.H.S. For any production in P1, the R.H.S. consists of either a single terminal (or λ in S→λ) or two or more variables.

    We define G2 = (N″, T, P2, S) as follows:

    All the productions in P1 are added to P2 if they are in the required form. All the variables in N1 are added to N″.

    Consider A→A1 A2….Am, where m≥3. We introduce new productions A→A1C1, C1→A2C2, …Cm2→Am1Am, and new variables C1, C2, …..Cm2. These are added to P″ and N″ respectively.

    Thus we get G2 in Chomsky Normal Form.

    Step 4: To complete the proof we have to show that L(G) = L(G1) = L(G2).

    To show that L(G)⊆L(G1), we start with w∈L(G). If A → X1, X2 …..Xn 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 X1X2….Xn. Thus L(G)⊆L(G1).

    Let w ∈ L(G1). To show that w∈L(G1), 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 P1. By construction of P1, 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 A1A2….Am wi, wm = w such that Ai wi. . Each Ai is either in N or a new variable, say Cai, When Ai∈N, Ai wi is a derivation in atmost k steps, and so by induction hypotheses, Ai wi. Thus (1) is true for all derivations. Therefore L(G) = L(G1).

    The effect of applying A→A1A2….Am in a derivation for w ∈ L(G1) can be achieved by applying the production A→A1C1, C1→A2C2, ……Cm2→Am1Am in P2.

    Hence it is easy to see that L(G1)⊆L(G2).

    To prove L(G2)⊆L(G1), we can prove an auxillary result.

    A w if A∈N1, A w        (2)

    Condition (2) can be proved by induction on the number of steps A w. Applying (1) to S, we get L(G2)⊆L(G1).

    Thus L(G) = L(G1) = L(G2)

  91. 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

    uv1xy1z∈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 uv1xy1z, 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).

  92. Using pumping lemma prove that the language (aibici ǀ≥1) is not context free.(6)

    Ans: The given language L = {an bn cn}

    Let z be any string that belongs to L

    Let z = aPbPcP∈L

    According to pumping lemma, if z is in L and |z|>n, z can be written as

    z = uvwxy

    z = aPbPcP as

    u, vwx and y respectively, we get

    u = aP

    vwx = bP     where |vwx|≤n

    vx = bPm     where |vx|≥1

    y = cP

    Substituting these values in uv1wx1y

    = uvi1vwx xi1y (uviwxiy is expressed in this form)

    = uvwx(vx)i1y

    = aPbP(bPm)i1cP

    = aPbPbP1miP + mcP∉L for all values of i

    Let i = 0.

    uvi1 vwx xi1 y = aPbPbP(0)m(0)P + micP

    = aPbPbmPcP

    = aPbmcPL

    Hence L is not a context free grammar.