Courses

# Test: Regular Languages & D-PDA

## 10 Questions MCQ Test Theory of Computation | Test: Regular Languages & D-PDA

Description
This mock test of Test: Regular Languages & D-PDA for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Regular Languages & D-PDA (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Regular Languages & D-PDA quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Regular Languages & D-PDA exercise for a better result in the exam. You can find other Test: Regular Languages & D-PDA extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

### Which of the following is analogous to the following? :NFA and NPDA

Solution:

All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.

QUESTION: 2

### Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.

Solution:

Using the permutation rule, we can calculate that there will be total of 625 permutations on 5 elements taking 4 as the length.

QUESTION: 3

### Which of the following relates to Chomsky hierarchy?

Solution:

he chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted

QUESTION: 4

A language is accepted by a push down automata if it is

Solution:

All the regular languages are the subset to context free languages and thus can be accepted using push down automata

QUESTION: 5

Which of the following is an incorrect regular expression identity?

Solution:

e is the identity for concatenation. Thus, eR=R.

QUESTION: 6

Which of the following strings do not belong to the given regular expression (a)*(a+cba).

Solution:

The string acbacba is unacceptable by the regular expression (a)*(a+cba).

QUESTION: 7

Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.

Solution:

Other mentioned options do not many of the combinations while option c seems most reliable.

QUESTION: 8

Which of the following strings is not generated by the given grammar:S->SaSbS|e

Solution:

All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.

QUESTION: 9

abb*c denotes which of the following?

Solution:

Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.

QUESTION: 10

The following denotion belongs to which type of language:G=(V, T, P, S)

Solution:

Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.