Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Test: Theory of Computation - 1 - Computer Science Engineering (CSE) MCQ

Test: Theory of Computation - 1 - Computer Science Engineering (CSE) MCQ


Test Description

10 Questions MCQ Test - Test: Theory of Computation - 1

Test: Theory of Computation - 1 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Theory of Computation - 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Theory of Computation - 1 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Theory of Computation - 1 below.
Solutions of Test: Theory of Computation - 1 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Theory of Computation - 1 solutions in Hindi for Computer Science Engineering (CSE) course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Theory of Computation - 1 | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Theory of Computation - 1 - Question 1

Which of the following is sufficient to convert an arbitrary Context Free Grammar (CFG) to an LL(1) grammar?

Detailed Solution for Test: Theory of Computation - 1 - Question 1

LL(1) Grammar: The first 'L' refers to scanning of input from Left to Right, the second 'L' refers to producing the Leftmost Derivation and the (1) stands for using only 1 lookahead input symbol at each step to make parsing action decisions. Hence, a context-free grammar G = (VT, VN, S, P) whose parsing table has no multiple entries is said to be LL(1) Grammar.
LL(1) Conflicts:

  • Checking whether a grammar is ambiguous or not is undecidable.
  • A grammar can be LL(1) only if it is not ambiguous, not left recursive and it must not contain left factoring and vice-versa is not necessary.
  • Any regular language can be LL(1) is true statement since we can write regular grammar which follows the above conflict.

Since a grammar is LL(1) only if it does not contain left recursion, ambiguity and left factoring, hence, to convert an arbitrary CFG to LL(1), all the three should be eliminated

Test: Theory of Computation - 1 - Question 2

Which of the following languages accept pumping lemma?

Detailed Solution for Test: Theory of Computation - 1 - Question 2

Pumping Lemma for Regular Languages: For any regular language L, if a string 'v' is pumped any number of times, it will still belong to the same language.
If L is a regular language, there exists an integer 'n' in which if all x∈L with |x|≥n, then there exists u,v,w∈Σ∗ such that x=uvw and it further follows the following conditions:


Pumping Lemma for Context-Free Languages: For any context-free language L, there exist two substrings that can be pumped any number of times and that string will still be following the same grammar.
If L is a context-free language, there exists an integer 'n' in which all x∈L with |x|≥n and there exists u,v,w,x,y∈Σ∗ such that x=uvwxy and it further follows the following conditions:

Recursive Languages: Recursive Languages do not follow the pumping lemma.

Recursively Enumerable Languages: Recursively Enumerable Languages do not follow the pumping lemma.

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Theory of Computation - 1 - Question 3

Which of the following languages is generated by the given grammar?
S → aS | bS | ϵ

Detailed Solution for Test: Theory of Computation - 1 - Question 3

S → aS | bS | ϵ 

This grammar results in (a + b)*

DFA for this grammar is:

Diagram

Now, consider the options one by one:

Option 1:

{anbm | n, m ≥ 0}

Here order is fixed, means first any number of a will come then any number of b. It is incorrect.

Option 2: 

{w ϵ {a, b} * | w has an equal number of a’s and b’s}

As given grammar is not generating the expression which generates only equal number of a and b. So,

not correct.

Option 3:

{an | n ≥ 0} {bn | n ≥ 0} {anbn | n ≥ 0}

Here, also order is fixed. So, it is incorrect.

Option 4:

{a, b}*

This is equivalent to (a + b)*. So, it is correct.

Test: Theory of Computation - 1 - Question 4

Identify the language generated by the following grammar, where S is the start variable.

S → XY

X → aX | a

Y → aYb | ϵ

Detailed Solution for Test: Theory of Computation - 1 - Question 4

Grammar:

S → XY

X → aX | a

Y → aYb | ϵ

Explanation:

X generates at least one a. Generates a string of type {a, aa, aaa, aaaa……}

ambn, if n = 0 and m = 0 ∴ string = ϵ which cannot be generated from the given grammar and hence option 2 is incorrect.

Y generates an equal number of a and b { ϵ, ab, aabb, ……} with a comes before b.

Since at least one a is generated by X and an equal number of a’s and b’s generated by Y ∴ m> n and hence option 1 is incorrect

The smallest length string generated by Y is ϵ. In ambn, n ≥ 0 and hence option 4 is incorrect.

{ a, aab, aaabb,………….} which is equivalent to :

L = {ambn | m > n, n ≥ 0}

Test: Theory of Computation - 1 - Question 5

Language L1 is defined by the grammar: S1 → aS1b|ϵ

Language L2 is defined by the grammar: S2 → abS2

Consider the following statements:

P: L1 is regular

Q: L2 is regular

Which one of the following is TRUE?

Detailed Solution for Test: Theory of Computation - 1 - Question 5

Suppose grammar G1:

S1 → aS1b|ϵ

It generates language in which number of a’s are equal to number of b’s and all a’s are followed by b’s

L1 = { abn | n ≥ 0}.

It is deterministic context free language. Extra memory is required for this. So, it can’t be accepted by finite state automata. L1 is not a regular language.

Now, another grammar let G2: S2 → abS2

This grammar also generates language in which number of a’s are equal to number of b’s. But it generates language L2 = { (ab)n | n ≥ 0 }

Regular expression for this = (ab)*

It doesn’t require any extra memory to remember the last string. It can be accepted by finite state automata. So, L2 is regular.

Test: Theory of Computation - 1 - Question 6

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?

Detailed Solution for Test: Theory of Computation - 1 - Question 6

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from aor from anbn. Both have a common prefix.

Test: Theory of Computation - 1 - Question 7

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?

Detailed Solution for Test: Theory of Computation - 1 - Question 7

Statement I: FALSE

If L1 ∪ L2 is regular, then neither L1 nor L2 needs necessarily be regular.

Example:

Assume L1= {an bn, n ≥ 0} over the alphabet {a, b} and L2 be the complement of L1.

Neither Lnor L2 is regular (both are DCFL) but L1 ∪ L2= {an bn} ∪ {an bn}c = (a + b)is regular.

Statement II: FALSE. The infinite Union of regular languages is not regular.

Example:

Given alphabet {a, b}.

L1= {ε}

L2= {ab}

L3= {aabb}

L4= {aaabbb}

:

:

L = L1 ∪ L2 ∪ L∪ L4 …

Each of the above are regular but their infinite Union gives L1= {an bn, n ≥ 0} which is not regular but DCFL.

Note:

DCFL → Deterministic context free language

Test: Theory of Computation - 1 - Question 8

For Σ = {a, b}, let us consider the regular language L = {x|x = a2+3k or x = b10+12k k ≥ 0}.

Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

Detailed Solution for Test: Theory of Computation - 1 - Question 8

Regular language L = {x|x = a2+3k or x = b10+12k k ≥ 0}.

L = {a2, a5, a8, a11 … ∪ b10, b22, b34…}

Pumping Lemma:

Let L be an infinite regular language. Then there exists some positive integer m such that any w ϵ L with |w|≥ m can be decomposed as

w = xyz

with |xy|≤ m such that wi = xyiz

is also L for all i = 0, 1, 2, …

Therefore, minimum Pumping Length should be 11, because string with length 10 (i.e., w = b10) does not repeat anything, but string with length 11 (i.e., w = b11) will repeat states.

Hence option 1, 2, and 3 are eliminated.

Therefore 24 can be the pumping lemma length.

Test: Theory of Computation - 1 - Question 9

Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________

Detailed Solution for Test: Theory of Computation - 1 - Question 9

A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.

Test: Theory of Computation - 1 - Question 10

A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation

Detailed Solution for Test: Theory of Computation - 1 - Question 10

Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.

Information about Test: Theory of Computation - 1 Page
In this test you can find the Exam questions for Test: Theory of Computation - 1 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Theory of Computation - 1, EduRev gives you an ample number of Online tests for practice

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)