Theory-of-Computation

Question 1
A
50
Question 1 Explanation: 

Question 2
 For a Turing machine M, <M> denotes an encoding of M. Consider the following two languages.
        L1=〈M〉|M takes more than 2021 steps on all inputs
L2=〈M〉|M takes more than 2021 steps on some input
Which one of the following options is correct?
A
Both L1and L2 are undecidable.
B
L1is undecidable and L2is decidable.
C
L1is decidable and L2is undecidable.
D
Both L1and L2 are decidable.
Question 2 Explanation: 

L1 is decidable. 

We can take all strings of length zero to length 2021.

If TM takes more than 2021 steps on above inputs then definitely it will take more than 2021 steps on all input greater than length 2021.

If TM takes less than 2021 steps:

In such a case suppose TM  takes less than 2021 steps (let's say  2020 steps ) for string length 2021, 2022, 2023, then definitely TM  will take 2020 steps for all input greater than 2023. Hence in both cases it is decidable.

 

Similarly L2 is also decidable. If we can decide for all inputs then we can decide for some inputs also.

Question 3
Consider the following language.

A
2
Question 3 Explanation: 

Option A accepts string “01111” which does not end with 011 hence wrong.

Option C accepts string “0111” which does not end with 011 hence wrong.

Option D accepts string “0110” which does not end with 011 hence wrong.

Option B is correct.

 

The NFA for language in which all strings ends with “011”

">
Question 4
Let <M> denote an encoding of an automaton M. Suppose that Σ = {0,1}. Which of the following languages is/are NOT recursive?
A
L = { | M is a DFA such that L(M) = Σ*}
B
L = { | M is a DFA such that L(M) = ∅}
C
L = { | M is a PDA such that L(M) = Σ*}
D
L = { | M is a PDA such that L(M) = ∅}
Question 4 Explanation: 
Question 5
Suppose that L1is a regular language and L2is a context free language. Which one of the following languages is NOT necessarily context free?
A
L1. L2
B
L1 ∪ L2
C
L1 ∩ L2
D
L1 − L2
Question 5 Explanation: 

L1. L2 =>  regular . CFL  == CFL. CFL  (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under concatenation so 

CFL. CFL= CFL  

Hence

Regular . CFL = CFL is true

 

L1 ∪ L2 => Regular ∪ CFL = CFL 

Regular ∪ CFL = CFL ∪ CFL  (as every regular is CFL so we can assume regular as CFL)

 

Since CFL is closed under union 

Hence Regular ∪ CFL = CFL   is true

 

L1 ∩ L2 => Regular ∩ CFL = CFL 

Regular languages are closed under intersection with any language

I.e,

Regular ∩ L = L  (where L is any language such as CFL, CSL etc)

 

Hence Regular ∩ CFL = CFL  is true

 

Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.

 

L1 − L2 => Regular − CFL = CFL 

=> Regular − CFL = regular ∩ CFL (complement)

Since CFL is not closed under complement so complement of CFL may or may not be CFL

 

Hence Regular − CFL need not be CFL

 

For ex:

R= (a+b+c)*  and L= {am bn ck | m ≠ n or n ≠ k} which is CFL.

 

The complement of L = {an bn cn | n>0} which is CSL but not CFL.

 

So 

R L = (a+b+c)* {am bn ck | m ≠ n or n ≠ k}

 

=> (a+b+c)* ∩  L (complement) 

=> (a+b+c)* ∩  {an bn cn | n>0}

=> {an bn cn | n>0}

 

Which is CSL. Hence Regular − CFL need not be CFL.

Question 6

In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

A
(L ∪ D)+
B
L(L ∪ D)*
C
(L⋅D)*
D
L⋅(L⋅D)*
Question 6 Explanation: 
Which is to be letter followed by any number of letters (or) digits
L(L ∪ D)*
Question 7

Consider a grammar with the following productions

S → a∝b|b∝c| aB
S → ∝S|b
S → ∝b b|ab
S ∝ → bd b|b 

The above grammar is:

A
Context free
B
Regular
C
Context sensitive
D
LR(k)
Question 7 Explanation: 
S ∝→ [violates context free]
Because LHS must be single non-terminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.
Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).
Question 8

Which of the following definitions below generates the same language as L, where L = {xnyn such that n >= 1}?

 I. E → xEy|xy
 II. xy|(x+xyy+)
 III. x+y+ 
A
I only
B
I and II
C
II and III
D
II only
Question 8 Explanation: 
(I) is the correct definition and the other two is wrong because the other two can have any no. of x and y. There is no such restriction over the number of both being equal.
Question 9

A finite state machine with the following state table has a single input x and a single out z.

If the initial state is unknown, then the shortest input sequence to reach the final state C is:

A
01
B
10
C
101
D
110
Question 9 Explanation: 

If A is the start state, shortest sequence is 10 'or' 00 to reach C.
If B is the start state, shortest sequence is 0 to reach C.
If C is the start state, shortest sequence is 10 or 00 to reach C.
If D is the start state, shortest sequence is 0 to reach C.
∴ (B) is correct.
Question 10

Let Σ = {0,1}, L = Σ* and R = {0n1n such that n >0} then the languages L ∪ R and R are respectively

A
regular, regular
B
not regular, regular
C
regular, not regular
D
not regular, no regular
Question 10 Explanation: 
L∪R is nothing but L itself. Because R is subset of L and hence regular. R is deterministic context free but not regular as we require a stack to keep the count of 0's to make that of 1's.
Question 11

Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let Lc be the complement of L over ∑*. Show that Lc is also in NP.

A
Theory Explanation.
Question 12

Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.

    I. L is deterministic context-free.
    II. L is context-free but not deterministic context-free.
    III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

A
II only
B
III only
C
I only
D
I and III only
Question 12 Explanation: 
L is DCFL.
We can make DPDA for this.

L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Question 13

Consider the following statements.

    I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
    II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

A
Both I and II
B
II only
C
Neither I nor II
D
I only
Question 13 Explanation: 
Statement I is wrong.
Assume L1 = {an bn | n>0} and L2 = complement of L1
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular, L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1 = {ab}
L2 = {aabb}
L3 = {aaabbb}
.
.
.
L100 = {a100 b100}
.
.
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……}
then we will get a new language L = {an bn | n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 14

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

A
10*(0*10*10*)*
B
((0 + 1)*1(0 + 1)*1)*10*
C
(0*10*10*)*10*
D
(0*10*10*)*0*1
Question 14 Explanation: 
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
Question 15

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

    L1 = | L(M) = Φ}
    L2 = {| M on input w reaches state q in exactly 100 steps}
    L3 = {| L(M) is not recursive}
    L4 = {| L(M) contains at least 21 members}
A
L2 and L3 only
B
L1 and L3 only
C
L2, L3 and L4 only
D
L1, L3 and L4 only
Question 15 Explanation: 
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 16

Consider the following language.

   L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3} 

The minimum number of states in a DFA that accepts L is ______.

A
6
Question 16 Explanation: 
DFA 1: No. of a’s divisible by 2.

DFA 1: No. of a’s not divisible by 3

Using product automata:
Question 17

Consider the following languages.

    L1 = {wxyx | w,x,y ∈ (0 + 1)+}
    L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?

A
L1 is context-free but not regular and L2 is context-free.
B
Neither L1 nor L2 is context-free.
C
L1 is regular and L2 is context-free.
D
L1 is context-free but L2 is not context-free.
Question 17 Explanation: 
L1 is regular. y can be expanded and w can also expanded. So x can be either "a" or "b".
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 18

Which two of the following four regular expressions are equivalent? (ε is the empty string).

    (i) (00)*(ε+0)
    (ii) (00)*
    (iii) 0*
    (iv) 0(00)*
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
Question 18 Explanation: 
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
Question 19

Which of the following statements is false?

A
The Halting problem of Turing machines is undecidable.
B
Determining whether a context-free grammar is ambiguous is undecidbale.
C
Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
D
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
Question 19 Explanation: 
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
Question 20

Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?

A
L = {x|x has an equal number of a's and b's } is regular
B
L = {anbn|n≥1} is regular
C
L = {x|x has more a's and b's} is regular
D
L = {ambn|m ≥ 1, n ≥ 1} is regular
Question 20 Explanation: 
L = {ambn|m ≥ 1, n ≥ 1}
Here, m and n are independent.
So 'L' Is Regular.
Question 21

If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

A
L1, L2
B
L1 ∩ L2
C
L1 ∩ R
D
L1 ∪ L2
Question 21 Explanation: 
Context free languages are not closed under intersection.
Question 22

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

A
the set of all binary strings with unequal number of 0’s and 1’s
B
the set of all binary strings including the null string
C
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
D
None of the above
Question 22 Explanation: 
(B) is the answer. Because for any binary string of 0's and 1's we can append another string to make it contain equal no. of 0's and 1's, i.e., any string over {0,1} is a prefix of a string in L.
Question 23

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

A
the sentence
if a then if b then c:=d
B
the left most and right most derivations of the sentence
if a then if b then c:=d
give rise top different parse trees
C
the sentence
if a then if b then c:=d else c:=f
has more than two parse trees
D
the sentence
if a then if then c:=d else c:=f
has two parse trees
Question 23 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 24

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

A
4
B
3
C
2
D
1
Question 24 Explanation: 
3 states are required in the minimized machine states B and C can be combined as follows:
Question 25

Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d  

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

A
Theory Explanation.
Question 26

Let Q = ({q1,q2}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.

(1) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)} 
A
Theory Explanation.
Question 27

Given Σ = {a,b}, which one of the following sets is not countable?

A
Set of all strings over Σ
B
Set of all languages over Σ
C
Set of all regular languages over Σ
D
Set of all languages over Σ accepted by Turing machines
Question 27 Explanation: 
Uncountable: Set of all languages over Σ is uncountable.
Question 28

Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

A
0*(1+0)*
B
0*1010*
C
0*1*01
D
0(10+1)*
Question 28 Explanation: 
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 29

Which one of the following is not decidable?

A
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
Question 29 Explanation: 
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 30

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?

 Note: wR  is the string obtained by reversing 'w'. 
A
{w⊂wR|w ∈ {a,b}*}
B
{wwR|w ∈ {a,b,c}*}
C
{anbncn|n ≥ 0}
D
{w|w is a palindrome over {a,b,c}}
Question 30 Explanation: 
(A) w⊂wR, can be realized using DPDA because we know the center of the string that is c here.
(B) wwR, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {anbncn | n ≥ 0} is CSL.
(D) {w | w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
Question 31

Choose the correct alternatives (More than one may be correct). Recursive languages are:

A
A proper superset of context free languages.
B
Always recognizable by pushdown automata.
C
Also called type ∅ languages.
D
Recognizable by Turing machines.
E
Both (A) and (D)
Question 31 Explanation: 
A) True, since there are languages which are not CFL still recursive.
B) False.
C) False, because Type-0 language are actually recursively enumerable languages and not recursive languages.
D) True.
Question 32

Choose the correct alternatives (More than one may be correct).

It is undecidable whether:
A
An arbitrary Turing machine halts after 100 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the products of two numbers.
D
None of the above.
E
Both (B) and (C).
Question 32 Explanation: 
A) An arbitrary TM halts after 100 steps is decidable. We can run TM for 100 steps and conclude that.
B) A TM prints a specific letter is undecidable.
C) A TM computes the products of two numbers is undecidable. Eventhough we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, undecidable.
Question 33

Choose the correct alternatives (More than one may be correct). Let R1 and R2 be regular sets defined over the alphabet Σ Then:

A
R1 ∩ R2 is not regular.
B
R1 ∪ R2 is regular.
C
Σ* − R1 is regular.
D
R1* is not regular.
E
Both (B) and (C).
Question 33 Explanation: 
Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleen-closure
Σ* - R1 is the complement of R1.
Hence, (B) and (C) are true.
Question 34

If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?

A
A ⊂ B
B
B ⊂ A
C
A and B are incomparable
D
A = B
Question 34 Explanation: 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
Question 35

Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.

A
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary
B
The numbers 1, 2, 4, ………………., 2n, …………..written in unary
C
The set of binary string in which the number of zeros is the same as the number of ones
D
The set {1, 101, 11011, 1110111, ………..}
Question 35 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 36

Regarding  the power of recognition of languages, which of the following statements is false?

A
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
B
Non-deterministic Push-down automata are equivalent to deterministic Push- down automata.
C
Non-deterministic Turing machines are equivalent to deterministic Push-down automata.
D
Both B and C
Question 36 Explanation: 
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
Question 37

The string 1101 does not belong to the set represented by

A
110*(0 + 1)
B
1 ( 0 + 1)* 101
C
(10)* (01)* (00 + 11)*
D
Both C and D
Question 37 Explanation: 
Options A & B are generates string 1101.
C & D are not generate string 1101.
Question 38

How many sub strings of different lengths (non-zero) can be found formed from a character string of length n?

A
n
B
n2
C
2n
D
Question 38 Explanation: 
Let us consider an example S = {APB}
Possible sub-strings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 39

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is

A
2
B
5
C
8
D
3
Question 39 Explanation: 
NFA:

Equivalent DFA:

Hence, 5 states.
Question 40

Which of the following statements is false?

A
Every finite subset of a non-regular set is regular
B
Every subset of a regular set is regular
C
Every finite subset of a regular set is regular
D
The intersection of two regular sets is regular
Question 40 Explanation: 
Let regular language L = a*b* and subset of L is anbn, n ≥ 0, which is not regular. Hence option (B) is false.
Question 41

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}* | w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}

A
Theory Explanation.
Question 42

Let M = ({q0, q1}, {0, 1}, {z0, x}, δ, q0, z0, ∅) be a pushdown automaton where δ is given by

    δ(q0, 1, z0) = {(q0, xz0)}
    δ(q0, ε, z0) = {(q0, ε)}
    δ(q0, 1, X) = {(q0, XX)}
    δ(q1, 1, X) = {(q1, ε)}
    δ(q0, 0, X) = {(q1, X)}
    δ(q0, 0, z0) = {(q0, z0)}

(a) What is the language accepted by this PDA by empty stack?

(b) Describe informally the working of the PDA.

A
Theory Explanation.
Question 43

(a) Let G1 = (N, T, P, S1) be a CFG where,
N = {S1, A, B}, T = {a,b} and
P is given by

         S1 → aS1b             S1 → aBb
         S1 → aAb              B → Bb
         A → aA                B → b
         A → a 

What is L(G1)?

(b) Use the grammar in part(a) to give a CFG
for L2 = {ai bj ak bl | i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.

(c) Is L2 inherently ambiguous?

A
Theory Explanation.
Question 44

(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions

Program → begin d semi X end
X → d semi X | sY
Y → semi s Y | ε 
A
Theory Explanation.
Question 45

Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite  automation  that  recognizes  the  language  represented  by  this  regular expression contains

A
n states
B
n + 1 states
C
n + 2 states
D
None of the above
Question 45 Explanation: 
Let's draw both NFA and DFA and see which one requires less no. of state.
DFA:

So, DFA requires (n+2) state.
NFA:

So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
Question 46

Context-free languages are closed under:

A
Union, intersection
B
Union, Kleene closure
C
Intersection, complement
D
Complement, Kleene closure
Question 46 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 47

Let LD be the set of all languages accepted by a PDA by final state and LE the set of all languages accepted by empty stack. Which of the following is true?

A
LD = LE
B
LD ⊃ LE
C
LE = LD
D
None of the above
Question 47 Explanation: 
For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.
Question 48

If L is context free language and L2 is a regular language which of the following is/are false?

A
L1 – L2 is not context free
B
L1 ∩ L2 is context free
C
~L1 is context free
D
~L2 is regular
E
Both A and C
Question 48 Explanation: 
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 - L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 - L2 is CFL. So False.
(B) As we said that CFL is closed under regular intersection. So True.
(C) CFL is not closed under complementation. Hence False.
(D) Regular language is closed under complementation.
Hence True.
Question 49

A grammar that is both left and right recursive for a non-terminal, is

A
Ambiguous
B
Unambiguous
C
Information is not sufficient to decide whether it is ambiguous or unambiguous
D
None of the above
Question 49 Explanation: 
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 50

(a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1)⊆L(M2). (note: strict subset)

A
Theory Explanation.
There are 50 questions to complete.

Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now