Theory of Computation

Practice Set – 0

This practice set covers the basic terminologies related to set theory.

Define the following terms and explain with appropriate example of each:

  1. Set
  2. Subset
  3. Proper superset
  4. Power set
  5. Symmetrical relation
  6. Injective function
  7. Surjective function
  8. Bijective function
  9. Equivalence relation
  10. Cartesian product

Practice Set – 1

This practice set covers the basic terminologies related to formal language and finite automata

Define the following terms and give example of each:

  1. Symbol
  2. Alphabet set
  3. String
  4. Language
  5. Finite language
  6. Infinite language
  7. Finite Automata
  8. Deterministic finite automata
  9. Non determinisitc finite automata
  10. Transition function

Practice Set – 2

This practice set contains the questions on the design of regular expression for the given regular language.

Design Regular Expressions for the following languages:

Design regular expression for following languages over alphabet set Σ = { a, b }

  1. L1 = Strings of even length
  2. L2 = Strings of odd length
  3. L3 = Strings of length divisible by 3
  4. L4 = Strings having exactly 2 a’s
  5. L5 = Strings having at least 2 a’s
  6. L6 = Strings having at most ‘2’ a’s
  7. L7 = Strings containing an even number of a’s
  8. L8 = Strings ending with the same symbols
  9. L9 = Strings ending with different symbols
  10. L10 = No two a’s should come together

Practice Set – 3

Design Push Down Automata for the following languages. Also, show the derivation of at least one string with the instantaneous descriptor. (The string length should be at least five). Also, show the graphical representation of each PDA

  1. L = {anbncn | n ≥ 1}
  2. L = {anbncn | n ≥ 0}
  3. L = {anbm | n > m, and n, m ≥ 1}
  4. L = {anbm | n < m, and n, m ≥ 1}
  5. L = {anb2n | n ≥ 1}
  6. L = {anb2n + 1 | n ≥ 1}

Practice Set – 4

Design Push Down Automata for the following languages. Also, show the derivation of at least one string with the instantaneous descriptor. (The string length should be at least five). Also, show a graphical representation of each PDA

  1. L = {anw | n ≥ 0, w ∈ {a, b}* and |w| ≤ n}
  2. L = {anbncm | n ≥ 0}
  3. L = {anbncm | n ≥ 1}
  4. L = {anbmcn | n ≥ 0}
  5. L = {anbmcn | n ≥ 1}
  6. L = {am+nbmcn | n ≥ 1}

Practice Set – 5

Design Push Down Automata for the following languages. Also, show the derivation of at least one string with the instantaneous descriptor. (String length should be at least five). Also, show the graphical representation of each PDA

  1. L = {ambm+ncn | n ≥ 1}
  2. L = {ambcm+n | n ≥ 1}
  3. L = {aibjck | i, j, k ≥ 0, i = j or i = k}
  4. L = {aibjck | i, j, k ≥ 0, j = i or j = k}
  5. L = {aibjck | i, j, k ≥ 0, k = j or k = j}
  6. L = {aibjck | i, j, k ≥ 0, i = j + k}

Practice Set – 6

Design Push Down Automata for the following languages. Also, show the derivation of at least one string with the instantaneous descriptor. (The string length should be at least five). Also, show the graphical representation of each PDA

  1. L = {aibjck | i, j, k ≥ 0, j = i + k}
  2. L = {aibjck | i, j, k ≥ 0, k = i + j}
  3. L = {aibjck | i, j, k ≥ 0, i > j + k}
  4. L = {aibjck | i, j, k ≥ 0, j > i + k}
  5. L = {aibjck | i, j, k ≥ 0, k > i + j}
  6. L = {w | w ∈ {a, b}*, and na(w) = nb(w)}

Practice Set – 7

Design Push Down Automata for the following languages. Also, show the derivation of at least one string with the instantaneous descriptor. (String length should be at least Five). Also show graphical representation of each PDA

  1. L = {w | w ∈ {a, b}*, and na(w) > nb(w)}
  2. L = {w | w ∈ {a, b}*, and na(w) < nb(w)}
  3. L = {w | w ∈ {a, b}*, and na(w) ≠ nb(w)}
  4. L = {wcwR | w ∈ {a, b}*}
  5. L = { Balanced strings of brackets }, ex. S → (S) | {S} | [S] | ε
  6. L = {aibjck | i ≠ j or j ≠ k}

Practice Set – 8

Convert the following Context Free Grammar to PDA:

  1. { S → AB, A → CD, B → b, C → a, D → a }
  2. { S → aAA, A → aS | bS | a }
  3. { S → AA | a, A → SA | b }
  4. { S → AA | a, A → SA | b }

Practice Set – 9

Conver following PDA to Context Free Grammar:

  1. δ(q0, 0, Z) = (q0, AZ),    δ(q0, 1, A) = (q0, AA),   δ(q0, 0, A) = (q1, ε)
  2. δ(q0, 0, Z) = (q0, AZ), δ(q0, 0, A) = (q0, AA), δ(q0, 1, A) = (q1, ε), δ(q1, 1, A) = (q1, ε), δ(q1, ε, A) = (q1, ε), δ(q1, ε, Z) = (q1, ε)
  3. Using pumping lemma, show that the language L = { aibici| i ≥ 1 } is not a CFL
  4. Using pumping lemma, show that the language L = { anbmcp | 0 ≤ n < m < p } is not a CFL

Practice Set – 10

  1. Design DFA for language over {0, 1} such that all strings begin and end with the same digit
  2. Design DFA to for the language L = { a3bwa3 | w is any string over {a, b}}
  3. Design FA for |w| mod 3 = 0, where w ∈ {a, b}*
  4. Design minimal DFA for w ∈ {a, b}* such that na(w) mod 3
  5. Deisgn DFA for strings having na(w) mod 3 > nb(w) mod 3
  6. Design DFA for strings that do not having ‘abb’ as substring
  7. Prove that 7 + 13 + 19 + … + (6n + 1) = n(3n + 4) using Mathematical induction
  8. Explain deductive proof and inductive proof

Important Notice:

Problem set 10 is to be solved by everyone. There are 10 other Practice sets (numbered from 0 to 9). You have to solve the practice set having the last digit of your enrollment number. For example, if your enrollment number is 190160107027, then you have to solve practice set 7, If your enrollment number is 200160107502 then you have to solve practice set 2, and so on. You have to submit a file including an index with proper problem descriptions and page numbers. You may refer video playlist at www.shorturl.at/inryW to solve the assignments.