Theory of computation miscellaneous

Theory of computation miscellaneous

Easy Questions

Theory of Computation

Theory of computation miscellaneous
  1. Consider the following grammar G :
    S → bS|aA|b
    A → bA |aB
    B → bB|aS| a
    Let Na (W) and Nb (W) denote the number of a 's and b 's in a string W respectively.
    The language L(G) ⊆ {a, b}+ generated by G is








  1. View Hint View Answer Discuss in Forum

    Here, we have
    S → bS
    S → baA (S → aA)
    S → baaB (A → aB)
    S → baaa (B → a)
    Therefore, | Na (w) | = 3.
    Also, if we use A → bA instead of A → aB,
    S → baA
    S → babA
    To terminate A, we would have to use A→ aB as only B terminates at a (B → a).
    S → baA
    S → babA
    S → babaB
    S → babaa
    Thus, here also, | Na (w) | = 3. So, C is the correct answer.

    Correct Option: C

    Here, we have
    S → bS
    S → baA (S → aA)
    S → baaB (A → aB)
    S → baaa (B → a)
    Therefore, | Na (w) | = 3.
    Also, if we use A → bA instead of A → aB,
    S → baA
    S → babA
    To terminate A, we would have to use A→ aB as only B terminates at a (B → a).
    S → baA
    S → babA
    S → babaB
    S → babaa
    Thus, here also, | Na (w) | = 3. So, C is the correct answer.

  1. Consider the following languages over the alphabet ∑ = {a, b, c}.
    Let L1 = { an bn cm | m , n ≥ 0 } and L2 = { { am bn cn | m , n ≥ 0 }
    Which of the following are context-free languages?
    I. L1 ∪ L2
    II. L1 ∩ L2








  1. View Hint View Answer Discuss in Forum

    The given language over Alphabets ∑ = (a, b, c) and the given language are :-
    L1 = { an bn cm | n , m ≥ 0 } is a CFL
    L2 = { am bn cn | n , m ≥ 0 } is also a CFL
    then union of two CFL is always CFL,
    L1 ∪ L2 = { an bm ck | (n = m) or (m = k), n , m ≥ 0 } is a context free language.
    Intersection of two CFL is may or may not be a context free language.
    L1 ∩ L2 = { an bm ck | (n = m) or (m = k) n , m ≥ 0 } or { an bn cn | n ≥ 0 } is a non context free language.
    Hence, option (a) is correct.

    Correct Option: A

    The given language over Alphabets ∑ = (a, b, c) and the given language are :-
    L1 = { an bn cm | n , m ≥ 0 } is a CFL
    L2 = { am bn cn | n , m ≥ 0 } is also a CFL
    then union of two CFL is always CFL,
    L1 ∪ L2 = { an bm ck | (n = m) or (m = k), n , m ≥ 0 } is a context free language.
    Intersection of two CFL is may or may not be a context free language.
    L1 ∩ L2 = { an bm ck | (n = m) or (m = k) n , m ≥ 0 } or { an bn cn | n ≥ 0 } is a non context free language.
    Hence, option (a) is correct.

  1. Let L1 , L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT ?
    I. L1 ∪ L2 is context-free.
    II. L1 is context-free.
    III. L1 – R is context-free.
    IV. L1 ∩ L2 is context-free.








  1. View Hint View Answer Discuss in Forum

    1. L1 ∪ L2 is context-free because the union of two context free language is always a context free or CFL are closed under union operation. So, it is correct.
    2. L1 is not context-free because CFL are not closed under complement operation. So, it is incorrect.
    3. L1 - R is context-free because if context-free language is intersection to the complement of regular language then it is always context-free. L1 - R = L1 ∩ R1, so it is correct.
    4. L1 ∩ L2 is not context-free because context-free languages are not closed under complement operations. So it is incorrect.

    Correct Option: B

    1. L1 ∪ L2 is context-free because the union of two context free language is always a context free or CFL are closed under union operation. So, it is correct.
    2. L1 is not context-free because CFL are not closed under complement operation. So, it is incorrect.
    3. L1 - R is context-free because if context-free language is intersection to the complement of regular language then it is always context-free. L1 - R = L1 ∩ R1, so it is correct.
    4. L1 ∩ L2 is not context-free because context-free languages are not closed under complement operations. So it is incorrect.

  1. Which of the following problems is undecidable?








  1. View Hint View Answer Discuss in Forum

    Finite state automata (FSA) has no undecidability CFL membership problem is also decidable. So option (b) i.e Ambiguity of CFL cannot be decidable.

    Correct Option: B

    Finite state automata (FSA) has no undecidability CFL membership problem is also decidable. So option (b) i.e Ambiguity of CFL cannot be decidable.

  1. Consider the following decision problems:
    P1. Does a given finite state machine accept a given string?
    P2. Does a given context-free grammar generate an infinite number of strings?
    Which of the following statements is true?








  1. View Hint View Answer Discuss in Forum

    In P1, A given finite state machine accepts a given string if it is decidable because in decidable problem there exists a turing machine that gives the correct answer for every statement in the domain of the problem. A class of problems with two outputs yes or no is said to be decidable (solvable), if there exist some definite algorithm which always terminates (halts) with one of the two outputs yes or no. Similarly, in P2 , the context-free grammar generates.

    Correct Option: A

    In P1, A given finite state machine accepts a given string if it is decidable because in decidable problem there exists a turing machine that gives the correct answer for every statement in the domain of the problem. A class of problems with two outputs yes or no is said to be decidable (solvable), if there exist some definite algorithm which always terminates (halts) with one of the two outputs yes or no. Similarly, in P2 , the context-free grammar generates.