Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  GATE Computer Science Engineering(CSE) 2025 Mock Test Series  >  Test: Identify Class Language - Computer Science Engineering (CSE) MCQ

Test: Identify Class Language - Computer Science Engineering (CSE) MCQ


Test Description

15 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Test: Identify Class Language

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

The language    over the alphabet 

Detailed Solution for Test: Identify Class Language - Question 1

   has only one comparison that can be done using a DPDA. Hence, its DCFL.

Context free languages are a proper subset of Recursive Languages. ∴ it is recursive too.

Test: Identify Class Language - Question 2

Which of the following is true for the language

Detailed Solution for Test: Identify Class Language - Question 2

We have algorithms to generate prime numbers ⇒ we can generate sequence of P for the given language, hence
strings as defined by the language definition.

So by Church Turing Thesis we can say that there exists a Turing Machine which can accept the given language.

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Identify Class Language - Question 3

Consider the following languages.

Detailed Solution for Test: Identify Class Language - Question 3

Both languages can be accepted by a DPDA :
L1 = start pushing element X into the stack on input 'a' ... start poping X on input 'b' ... move to final state when stack empty and input = 'c'

L2 = start pushing elements XX into the stack on input 'a' ... start poping X on input 'b' ... move to final state when stack
empty and input = 'epsilon'

so (A) and (D) are False

L1 ∪ L2 is a CFL ... we can build it by having L1, L2 and an extra state ... and an 'epsilon' transition to both L1 and L2 from
that extra state.

so (C) is false

L1 ∩ L2 = Phi because we have no string aibj where i=j and i=2j for i,j>=1
and clearly L1 is not a regular language

 

Test: Identify Class Language - Question 4

Let    are languages as defined below:

Then L is

Detailed Solution for Test: Identify Class Language - Question 4

which is context free but not regular.

Test: Identify Class Language - Question 5

Consider the languages

Detailed Solution for Test: Identify Class Language - Question 5

All are context free.
L1 -> Push 0 on stack and when 1 comes, start popping. If stack becomes empty and 1's are remaining start pushing 1. At
end of string accept if stack is non- empty.
L2 -> Do the same as for L1, but accept if stack is empty at end of string.
L3 -> Do, the same as for L2, but for each 0, push two 0's on stack and start the stack with a 0.
L4 -> Do the same as for L1, but for each 0, push two 0's on stack
All are in fact DCFL. Pushing two 0's on stack might sound non-trivial but we can do this by pushing one symbol and going
to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.

Test: Identify Class Language - Question 6

Consider the languages L1,L2 and L3 as given below.

and

Which of the following statements is NOT TRUE?

Detailed Solution for Test: Identify Class Language - Question 6

Turning Machine is powerful Machine it can be used to accept all the languages (RL,CFL,CSL,RE)

Test: Identify Class Language - Question 7

Consider the following languages.

Which one of the following statements is FALSE?

Detailed Solution for Test: Identify Class Language - Question 7

Explanation: (B) is false.

L1 is regular, so its complement would also be regular.

L1 is a regular language of the form 0^* 1^* 0^*. L2 on the other hand is a CFL as it can be derived from the following CFG
L2 = { 0^p 1^q 0^r | p,q,r>0   And p notEqualTo r }
S -> AC|CA
C -> 0C0|B
A -> 0A|0
B -> 1B|epsilon
If coming up with a CFG for L2 is difficult, one can intuitively see that by reducing it to a simpler problem. L2 is very similar to a known CFL L3 = { a^m b^l | m notEqualTo n }

(A) L2 is context free, which is true [CORRECT]
(B) L1 intersection L2 is context free, which is again true because L1 is a regular language and L2 is a CFL. RL union CFL is always a CFL. Hence [CORRECT]
(C) Complement of L2 is recursive, which is true due to the fact that complement of a CFL is CSL for sure (Context sensitive language), which in turn (CSL) is a subset of recursive languages. Hence [CORRECT]
(D) Complement of L1 is context free but not regular, which is false due to closure laws of regular languages. Complement of a RL is always a RL. Hence [INCORRECT]

Test: Identify Class Language - Question 8

Consider the following languages over the alphabet  

Here, ωr is the reverse of the string . Which of these languages are deterministic Context-free languages?

Detailed Solution for Test: Identify Class Language - Question 8

C.
L3 is CFL and not DCFL as in no way we can deterministically determine the MIDDLE point of the input string.

Test: Identify Class Language - Question 9

Consider the context-free grammars over the alphabet    given below.  S and T are non-terminals.

Detailed Solution for Test: Identify Class Language - Question 9

Since while intersection all strings produced by production aSb in G1 and bSa in G2 will be 0
so only common production will be
S-->T
T-->cT | epsilon
which is nothing but c* hence it is REGULAR and INFINITE

Test: Identify Class Language - Question 10

Consider the following languages.

Which of the following are CORRECT?

Detailed Solution for Test: Identify Class Language - Question 10

L1 is Csl,L2 is context free
L3 is not Context free and L4 is Dcfl

Test: Identify Class Language - Question 11

Let L consist of all binary strings beginning with a 1 such that its value when converted to decimal is divisible by 5. Which of the following is true?

Detailed Solution for Test: Identify Class Language - Question 11

l can be recognized by a dfa. we have a dfa to accept all such strings which when interpretated as decimal number are
divisible by n. where n can be anything the dfa of such can be made by a trick.
states are equal to possible remainders

if u can see the symmetry in it. write states and make fill like q0 q1 q2 q3 ...
now it is saying that it has to always start with 1 which the above dfa will not satisfy so make it a nfa by making a
transition from q0 on zero to a new dead state. now you have a nfa reduce it which will result in a deterministic dfa .

Test: Identify Class Language - Question 12

Consider the following languages over the alphabet {0,1}.

Where xr is the reverse of string x; e.g. 011R =110 Which of the following is true?        

Detailed Solution for Test: Identify Class Language - Question 12

Test: Identify Class Language - Question 13

Let L be a given context-free language over the alphabet   . Construct L1 ,L2  as follows. Let                 

Detailed Solution for Test: Identify Class Language - Question 13

L2 = L.L

Context free languages are closed under Concatenation.

So L2 is Context Free Language.

Test: Identify Class Language - Question 14

Let     be a one letter alphabet and     be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let L1 and L be the set of languages over  ∑1 and   ∑2    respectively. Which of the following is true about L1 and L:  

Detailed Solution for Test: Identify Class Language - Question 14

languages over alphabet set are uncountable so ans should be e

Test: Identify Class Language - Question 15

Consider the following grammar  G with terminals     start symbol S , and non-terminals 

A language L is called prefix-closed if for every     every prefix of X is also in L . Which of the following is FALSE?

Detailed Solution for Test: Identify Class Language - Question 15

The given grammar generates balanced parenthesis.

Lets take a smallest string : [ [ ] ] (say x )
Prefixes of x are : [ , [ [ ,[ [ ]

BUT they don't belong to the langauge generated by the given grammar.

SO, the answer will be Option D

 

55 docs|215 tests
Information about Test: Identify Class Language Page
In this test you can find the Exam questions for Test: Identify Class Language solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Identify Class Language , EduRev gives you an ample number of Online tests for practice

Up next

Download as PDF

Up next