# Multiple choice question for engineering

## Set 1

1. The entity which generate Language is termed as:

a) Automata

b) Tokens

c) Grammar

d) Data

### View Answer

2. Production Rule: aAb->agb belongs to which of the following category?

a) Regular Language

b) Context free Language

c) Context Sensitive Language

d) Recursively Ennumerable Language

### View Answer

3. Which of the following statement is false?

a) Context free language is the subset of context sensitive language

b) Regular language is the subset of context sensitive language

c) Recursively ennumerable language is the super set of regular language

d) Context sensitive language is a subset of context free language

### View Answer

4. The Grammar can be defined as: G=(V, ∑, p, S)

In the given definition, what does S represents?

a) Accepting State

b) Starting Variable

c) Sensitive Grammar

d) None of these

### View Answer

5. Which among the following cannot be accepted by a regular grammar?

a) L is a set of numbers divisible by 2

b) L is a set of binary complement

c) L is a set of string with odd number of 0

d) L is a set of 0^{n}1^{n}

### View Answer

^{n}1

^{n}. For other options, it is possible to make a dfa or nfa representing the language set.

6. Which of the expression is appropriate?

For production p: a->b where a∈V and b∈_______

a) V

b) S

c) (V+∑)*

d) V+ ∑

### View Answer

7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?

a) Non regular language

b) 0^{n}1^{n} | n>=0

c) 0^{n}1^{n} | n>=1

d) None of the mentioned

### View Answer

^{n}1

^{n}}. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.

8. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is

a) 3

b) 7

c) 5

d) 6

### View Answer

9. Which of the following statement is correct?

a) All Regular grammar are context free but not vice versa

b) All context free grammar are regular grammar but not vice versa

c) Regular grammar and context free grammar are the same entity

d) None of the mentioned

### View Answer

10. Are ambiguous grammar context free?

a) Yes

b) No

### View Answer

## Set 2

1. What kind of expressions do we used for pattern matching?

a) Regular Expression

b) Rational Expression

c) Regular & Rational Expression

d) None of the mentioned

### View Answer

2. Which of the following do Regexps do not find their use in?

a) search engines

b) word processors

c) sed

d) none of the mentioned

### View Answer

3. Which of the following languages have built in regexps support?

a) Perl

b) Java

c) Python

d) C++

### View Answer

4. The following is/are an approach to process a regexp:

a) Contruction of NFA and subsequently, a DFA.

b) Thompson’s Contruction Algorithm

c) Both (a) and (b)

d) None of the mentioned

### View Answer

5. Are the given two patterns equivalent?

(1) gray|grey

(2) gr(a|e)y

a) yes

b) no

### View Answer

6. Which of the following are not quantifiers?

a) Kleene plus +

b) Kleene star *

c) Question mark ?

d) None of the mentioned

### View Answer

7. Which of the following cannot be used to decide whether and how a given regexp matches a string:

a) NFA to DFA

b) Lazy DFA algorithm

c) Backtracking

d) None of the mentioned

### View Answer

8. What does the following segment of code output?

$string1 = "Hello Worldn"; if ($string1 =~ m/(H..).(l..)/) { print "We matched '$1' and '$2'.n"; }

a) We matched ‘Hel’ and ‘ld’

b) We matched ‘Hel’ and ‘lld’

c) We matched ‘Hel’ and ‘lo ‘

d) None of the mentioned

### View Answer

9. Given segment of code:

$string1 = "HellonWorldn"; if ($string1 =~ m/dnz/) { print "$string1 is a string "; print "that ends with 'dn'.n"; }

What does the symbol /z does?

a) changes line

b) matches the beginning of a string

c) matches the end of a string

d) none of the mentioned

### View Answer

10. Conversion of a regular expression into its corresponding NFA :

a) Thompson’s Construction Algorithm

b) Powerset Construction

c) Kleene’s algorithm

d) None of the mentioned

### View Answer

## Set 3

1. The transition a Push down automaton makes is additionally dependent upon the:

a) stack

b) input tape

c) terminals

d) none of the mentioned

### View Answer

2. A PDA machine configuration (p, w, y) can be correctly represented as:

a) (current state, unprocessed input, stack content)

b) (unprocessed input, stack content, current state)

c) (current state, stack content, unprocessed input)

d) none of the mentioned

### View Answer

3. |-* is the __________ closure of |-

a) symmetric and reflexive

b) transitive and reflexive

c) symmetric and transitive

d) none of the mentioned

### View Answer

4. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?

a) process the whole string

b) end in final state

c) end with an empty stack

d) all of the mentioned

### View Answer

5. A DPDA is a PDA in which:

a) No state p has two outgoing transitions

b) More than one state can have two or more outgoing transitions

c) Atleast one state has more than one transitions

d) None of the mentioned

### View Answer

6. State true or false:

Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.

a) true

b) false

### View Answer

7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:

a) rejected

b) goes into loop forever

c) both (a) and (b)

d) none of the mentioned

### View Answer

8. A language accepted by Deterministic Push down automata is closed under which of the following?

a) Complement

b) Union

c) Both (a) and (b)

d) None of the mentioned

### View Answer

9. Which of the following is a simulator for non deterministic automata?

a) JFLAP

b) Gedit

c) FAUTO

d) None of the mentioned

### View Answer

10. Finite-state acceptors for the nested words can be:

a) nested word automata

b) push down automata

c) ndfa

d) none of the mentioned

### View Answer

## Set 4

1. The password to the admins account=”administrator”. The total number of states required to make a password-pass system using DFA would be __________

a) 14 states

b) 13 states

c) 12 states

d) A password pass system cannot be created using DFA

### View Answer

2. Which of the following is the corresponding Language to the given DFA?

a) L= {x ϵ {0, 1} * | x ends in 1 and does not contain substring 01}

b) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 00}

c) L= {x ϵ {0,1} |x ends in 1 and does not contain substring 00}

d) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 11}

### View Answer

3. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:

a) {Hello, World, Input, Output, ε}

b) {Hello, World, ε}

c) {Input, Output, ε}

d) {}

### View Answer

4. Let the given DFA consist of x states. Find x-y such that y is the number of states on minimization of DFA?

a) 3

b) 2

c) 1

d) 4

### View Answer

5. For a machine to surpass all the letters of alphabet excluding vowels, how many number of states in DFA would be required?

a) 3

b) 2

c) 22

d) 27

### View Answer

6. For the DFA given below compute the following:

Union of all possible combinations at state 7,8 and 9.

a) {aba, ac, cc, ca, cb, bc, bab, ca}

b) {bab, bc, ac, aba, ca, aac, ccb}

c) {cc, ca, cb, aba, bab, ac}

d) {aba, ac, cc, ca, cb, bc, bab, caa}

### View Answer

7. Given L= {Xϵ∑*= {a, b} |x has equal number of a, s and b’s}.

Which of the following property satisfy the regularity of the given language?

a) Regularity is dependent upon the length of the string

b) Regularity is not dependent upon the length of the string

c) Can’t be said for a particular string of a language

d) It may depend on the length of the string

### View Answer

8. Given:

L= {xϵ∑= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?

a) Yes

b) No

### View Answer

9. δ(A,1) = B, δ(A,0) =A

Δ (B, (0,1)) =C

δ(C,0) = A (Initial state =A)

String=”011001” is transit at which of the states?

a) A

b) C

c) B

d) Invalid String

### View Answer

## Set 5

1. Which of the following is same as the given DFA?

a) (0+1)*001(0+1)*

b) 1*001(0+1)*

c) (01)*(0+0+1)(01)*

d) None of the mentioned

### View Answer

2. Which of the following statements is not true?

a) Every language defined by any of the automata is also defined by a regular expression

b) Every language defined by a regular expression can be represented using a DFA

c) Every language defined by a regular expression can be represented using NFA with e moves

d) Regular expression is just another representation for any automata definition

### View Answer

3. The total number of states required to automate the given regular expression

(00)*(11)*

a) 3

b) 4

c) 5

d) 6

### View Answer

4. Which of the given regular expressions correspond to the automata shown?

a) (110+1)*0

b) (11+110)*1

c) (110+11)*0

d) (1+110)*1

### View Answer

5. Generate a regular expression for the following problem statement:

Password Validation: String should be 8-15 characters long. String must contain a number, an Uppercase letter and a Lower case letter.

a) ^(?=.*[a-z])(?=.*[A-Z])(?=.*d).{8,15}$

b) ^(?=.*[a-z])(?=.*[A-Z])(?=.*d).{9,16}$

c) ^(?=.[a-z])(?=.[A-Z])(?=.d).{8,15}$

d) None of the mentioned

### View Answer

6. Generate a regular expression for the following problem statement:

P(x): String of length 6 or less for å={0,1}*

a) (1+0+e)6

b) (10)6

c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)

d) More than one of the mentioned is correct

### View Answer

7. The minimum number of states required in a DFA (along with a dumping state) to check whether the 3rd bit is 1 or not for |n|>=3

a) 3

b) 4

c) 5

d) 1

### View Answer

8. Which of the regular expressions corresponds to the given problem statement:

P(x): Express the identifiers in C Programming language

l=letters

d=digits

a) (l+_)(d+_)*

b) (l+d+_)*

c) (l+_)(l+d+_)*

d) (_+d)(l+d+_)*

### View Answer

9. Generate a regular expression for the given language:l

L(x): {xÎ{0,1}*| x ends with 1 nd does not contain a substring 01}

a) (0+01)*

b) (0+01)*1

c) (0+01)*(1+01)

d) All of the mentioned

### View Answer

10. The minimum number of transitions to pass to reach the final state as per the following regular expression is:

{a,b}*{baaa}

a) 4

b) 5

c) 6

d) 3