TOC Nptel

Assignment 1

1.Which of the following is an example of finite state systems ?

    a) Text editor

    b) Elevator

    c) Control unit of a computer

    d) All of the above

Ans: All of the above

2.Given an arbitrary NFA with n states, the maximum number of states

   in equivalent DFA is

1. n

2. 2n

3. n2

4. None of the above

Ans:2n

3.Which of the status are final/accepting state of the following automata?

1. q0

2. q1,q3,q6

3. q5,q6

4. q2,q4,q5

Ans:q5,q6

4.Which of the following forms a DFA ?

   a) (Q, Σ, 𝛿, q0, F)

   b) (Q, Σ, 𝛿, F)

   c) (Q, 𝛿, q0, F)

   d) (Q, Σ, 𝛿, F)

Ans:(Q, Σ, 𝛿, q0, F)

5.Which of the following is the transition table of the given DFA ?

Ans:d)

6.What is E of a given DFA with E as alphabet ?

   a) Language over Σ

   b) Dual of V

   c) Empty language

   d) All possible strings over Σ

Ans:All possible strings over Σ

7.Which of the following strings is accepted by the given DFA ?

   a) 011110

   b) 101011

   c) 010100

   d) 111000

Ans:011110

8.Which of the following is the definition of extended transition function?

a) δ(q,w) = δ(q, xa) = δ(δ(q,x), a)

b) δ(q,w) = δ(q, xa) = 𝛿(δ(q,x), a) 

c) δ(q,w) = 𝛿(q, xa) = 𝛿(𝛿(q,x), a)

(d) None of the above

Ans:δ(q,w) = δ(q, xa) = 𝛿(δ(q,x), a)

9.Which state the given DFA reaches after processing the string w =1011?

1. q1 

2. q2

3. q3

4. q4

Ans:q2

10.

The given DFA accepts which of the following:

   a) All strings starting with 1

   b) All strings ending with 1

   c) All strings starting with 0

   d) All strings ending with 0

Ans:All strings starting with 1

11.Which of the following should be the final state if the given DFA were to accept all strings           

     ending with 01?

1. q0

2. q1

3. q2

4. q3

Ans:q2

12.Which is not true for regular language?

a) Language of DFA

b) Language of NFA

c) Set off all strings that take starting state to one of accepting states

d) All of the above is false

Ans:All of the above is false

13.The given DFA accepts

1. All strings starting with 1

2. All strings starting with 0

3. All strings starting with 1 of even length

4. All strings starting with 0 of even length

Ans:All strings starting with 1 of even length

14.What should in the blank space shown in the diagram for the given figure to a DFA ?

1. 0

2. 1

3. A

4. Any symbol will make it a DFA

Ans:1

15.

       Is the given figure a DFA ?

1. Yes

2. No

Ans:No

Assignment 2

1.This DFA accepts which strings from given options?

1. All the strings with same symbol

2. All strings of even length

3. All strings ending with different symbols

4. None of the above

Ans:All strings ending with different symbols

2.Out of the given NFAs, which are equivalent to the above questions

1. Both I& II

2. Neither I or II

3. Only I

4. Only II

Ans:Only I

3.Given an arbitrary NFA with n states, the maximum number of states

   in equivalent DFA is

1. n

2. 2n

3. n2

4. None of the above

Ans:2n

.

4.Given L = {ab, baa} which of the following is not in L*

1. ababaaab

2. baaabbaa

3. abbaaab

4. ababbaaab

Ans:ababaaab

5.Given transition table applies to which NFA?

Ans:c)

6.Given NFA accepts strings of which of the given options

1. All strings ending with 00

2. All strings ending with 00, including empty string

3. All strings containing 00

4. All strings containing 00 including empty string

Ans:All strings containing 00 including empty string

7.For given NFA, in the given transition table of the equivalent DFA after subset construction, correct?

1. True

2. False

Ans:False

8.For given NFA, is the given DFA equivalent

1. True

2. False

Ans:False

9.Is the following statement about 𝛿D, the transition function of the DFA we get via subset construction, correct?

𝛿D(s, a) =∪p∈S𝛿N(p, a)

where S ∈ QD ie. S C QN and 𝛿N is transition function of NFA.

1. True

2. False

Ans:True

10.Will bababab be accepted by given NFA?

 

1. Yes

2. No

3. Sometimes

4. None of the above

Ans:Yes

11.All DFAs are NFAs. True or False ?

1. True

2. False

Ans:True

12.Is an NFA more powerful than a DFA?

1. True

2. False

Ans:False

13.The number of states in minimum DFA corresponding to the language

     (0+1)*(10)

1. 2

2. 3

3. 4

4. 5

Ans:3

14.Which of the following are true?

1. NFA computes on multiple paths simultaneously

2. NFA computes on multiple paths but not simultaneously

3. NFA computes on only single path

4. None of the above

Ans:NFA computes on multiple paths simultaneously

15.Which string is not accepted by given NFA

1. 1000101

2. 111010111

3. 1100001

4. 1000110

Ans:1000110

Assignment 3

21.Let L be a language defined as follow: L = {ap | p is a prime} which of the following are true?

1. L is not a regular language.

2. L is a regular language (where is the Kleene closure).

3. L is a regular language

4. None of the above is true

Ans:L is not a regular language.

L is a regular language (where is the Kleene closure).

22.What is the language corresponding to the following regular expression? (0 + 1)*(01 + 10)(0 + 1)*

1. {w | w contains 01 or 10 as a substring}

2. {w | length of w is >= 2}.

3. {w | w  ∈ {0,1}*}.

4. {w | w contains atleast one 0 and one 1}.

Ans:{w | w contains 01 or 10 as a substring}

       {w | w contains atleast one 0 and one 1}

23.Consider the following grammar, S→AaA,A→bA | Ab | Ac | cA | aaA | Aaa | aAa | ε. Which of the following strings are not generated by the above grammar?

1. a20b21c23

2. a21b22c20

3. b21a22c20

4. c21b22a20

Ans:a20b21c23

       b21a22c20

            c21b22a20

24.Let L be a language defined as follow, L = (w| w ∈ {0, 1}* and w contains odd number on 1's} which of the following regular expression corresponds to above language?

1. (0 + 10*1)*1

2. 0*10*(10*10*)*

3. 0*1(0 + 10* 1)*

4. None of the above.

Ans:0*10*(10*10*)*

       0*1(0 + 10* 1)*

25.Consider the following languages, A={anbm | n,m>=0},B={anbm | n>=m>=0},C={anbm | n=m>=0},D={anbm | n>=m<=100}.

Which of the above are not regular?

1. Only B and D.

2. Only C.

3. Only B and C.

4. All of them.

Ans:Only B and C

26.Which of the following statements are true?

1. Union of two non-regular languages is non-regular.

2. Intersection of a non-regular language and a regular language is non-regular.

3. Kleene closure of a non-regular language is non-regular.

4. Union of a non-regular language with its complement is regular.

1. 1,2 and 3

2. 1,3 and 4

3. 2 and 3

4. Only 4

Ans:Only 4

27.Number of states in the minimized DFA of the following DFA will be,

1. 1

2. 2

3. 3

4. 4

Ans:4

28.Which of the following languages are regular?

A = (x | x has two O's separated by the number of positions that is a multiple of 4. }

B = {x | x is binary representation of multiple of 3}

C = (x | x is a binary string and decimal of any prefix of x is not of form 3m + 2, where m>=0}

1. Only B and C.

2. Only B.

3. A, B and C.

4. Only A.

Ans: A,B, and C

29.For languages A and B we define following operations,

Shuffle(A, B) = {w l w = a1b1 . ... akbk, where a1 ... ak ∈ A and b1 ... bk ∈ B and each ai, bi ∈ Σ*}. Perfect Shuffle(A, B) = {w | w = a1,b1... akbk, where a1 ... ak ∈ A and b1 ... bk ∈ B and each ai, bi ∈ Σ }. FirstHalves(A) = (x | 3y, |x|= |y| and xy ∈ A}.

If A and B are regular then which of the above is regular?

1. Only Shuffle(A, B) and PerfectShuffle(A, B).

2. Only First Halves(A).

3. Shuffle(A, B), PerfectShuffle(A, B) and First Halves(A).

4. None of them is regular.

Ans:Shuffle(A, B), PerfectShuffle(A, B) and First Halves(A).

30.what is the language of the following DFA?

1. w | w contains at least three 0s}

2. {w | w contains number of 0 as a multiple of 3 and number of 1 as a multiple of 2}

3. {w | w contains at least three 0s and two ls}

4. {w | w contains at least three 0s and even number of 1s}

Ans:{w | w contains at least three 0s and two ls}

Assignment 5

41.Which of the following statements are true?

1. A PDA is an NFA with a stack.

2. Size of the stack of a PDA is finite.

3. PDAs and CFGs are equivalent.

4. None of the above is true.

Ans:A PDA is an NFA with a stack.

       PDAs and CFGs are equivalent.

42.Consider the following languages A and B,

      A = (0i1j | i,j >= 0, (i + j) is divisible by 2}

      B = {i1j | i,j >=0} 

      which of the following statements are true?

1. A and B are not CFL.

2. A is a CFL but not regular.

3. B - A is a CFL but not regular.

4. A and B are both regular.

Ans:A and B are both regular.

43.What is the language accepted by the following PDA?

1. {w | w ∈ {0, 1}+}.

2. {w l w is of form xxr, where x ∈ (0, 1}+ . }

3. {w | w is a palindrome}

4. {w | w is an odd length palindrome}

Ans:{w | w is an odd length palindrome}

44.What is the language of the following grammar?

     S → aS1bS3c | aS4bS1c

     S1 → aS1b | ε

     S2 → bS2c | ε

     S3→ S3c | ε

     S4 → S4a | ε

1. {aibjck | i + j >= k}

2. {aibjck | i + j = k}

3. {aibjck | 1 = j = k}

4. {aibjck | i = j or j = k}

Ans:{aibjck | i = j or j = k}

45.Consider the following languages A and B,

A = {ai bj | i > j}, 

B = {bkal | k > I},

which of the following statement are true

1. A . B is a regular language.

2. A* U B* is a regular language.

3. (A* U B*)* is a CFL but not a regular language.

4. A . B is a CFL but not regular.

Ans:A . B is a CFL but not regular.

46.Consider the following language,

     A = (ww | w ∈ Σ+ },

    which of the following statements are true?

1. Both A and A(bar) are CFLs.

2. A is a CFL but A(bar) is not a CFL.

3. A(bar) is a CFL but A is not a CFL.

4. Both A and A(bar) are not CFLs.

Ans:A(bar) is a CFL but A is not a CFL

47.Which of the following languages are CFLs?

A = {wwrwrw | w ∈ Σ*},

B = {wwrxxr | w,x ∈ Σ*},

C = {aibjakbl | i, j, k, I >= 0, (i + j) = (k + l)} 

1. Only B.

2. Only A and B.

3. Only B and C.

4. All of them.

Ans:Only B and C

48.Which of the following statements are true?

1. An NFA has an equivalent DFA.

2. An NPDA has an equivalent DPDA.

3. NFAs are more powerful that DFAS.

4. NPDAs are more powerful that DPDAs.

Ans:An NFA has an equivalent DFA.

       NPDAs are more powerful that DPDAs.

49.For a language A, consider the following, 

     Suffix(A) = {v | uv ∈ A for some string u}, 

     which of the following statements are true?

1. If A is a CFL then Suffix(A) is also a CFL.

2. If A is a CFL then Suffix(A) is not a CFL.

3. If A is a CFL then Suffix(A) may or may not be a CFL.

4. None of the above is true.

Ans:If A is a CFL then Suffix(A) is also a CFL.

50.What is the language accepted by the following PDA?

1. {aibic2i | i>=0}

2. {aibjck | i, j, k >= 0}

3. {aibjci+j | i,j >= 0}

4. {aibici | i>= 0}

Ans:{aibjci+j | i,j >= 0}