Type Here to Get Search Results !

# Formal Languages And Automation Theory MCQs With Answers - Set V

0

Formal Languages And Automation Theory MCQs

Set V

Q1. Regular expression for all strings starts with ab and ends with ba is.

a) aba*b*ba

b) ab(ab)*ba

c) ab (a+b)*ba

d) All of the mentioned

Explanation : The givem string ab (a+b)*ba starts with ab and ends with ba

Q2. L is a regular Language if and only If the set of __________ classes of IL is finite.

a) Equivalence

b) Reflexive

c) Myhill

d) Nerode

Explanation : This is according to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.

Q3. The generators of languages are ________________

a) Regular expression

b) Grammars

c) FSM

d) All

Explanation : Grammars is usually thought of as a language generator. However, it can also sometimes be used as the basis for a "recognizer"—a function in computing that determines whether a given string belongs to the language or is grammatically incorrect.

Q4. A language can be generated from simple primitive language in a simple way if and only if

a) It is recognized by a device of infinite states

b) It takes no auxiliary memory

c) Both are correct

d) Both are wrong

Answer is b) It takes no auxiliary memory
Explanation : A language is regular if and only if it can be accepted by a finite automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is shut down.

Q5. The regular expression of language which is starting and ending with different symbols is __________________

a) a(a+b)*b

b) b(a+b)*a

c) a(a+b)*b + b(a+b)*a

d) All

Answer is c) a(a+b)*b + b(a+b)*a
Explanation : For explanation Join the discussion below

Q6. Context Free Grammars has ________tuples

a) 5

b) 4

c) 3

d) None

Explanation : Context free grammar G can be defined by four tuples as: G= (V, T, P, S)

Q7. A grammar is said to be ambiguous grammar if it :-

a) produces more than one derivation tree

b) produces more than one left most derivation

c) produces more than one right most derivation

d) All

Explanation : The grammear that satisfies all the mentioned options is ambitious

Q8. Backtracking is allowed in

a) NDFA

b) DFA

c) Both a & b

d) None

Explanation : The transition from a state is to a single particular next state for each input symbol. Hence it is called deterministic which allows backtracking

Q9. (a + b)(cd)*(a + b) denotes the following set

a) {a(cd)nb|n = 1}

b) {a(cd)na|n = 1} ? {b(cd)nb/n = 1}

c) {a(cd)na|n = 0} ? {a(cd)nb/n = 0} ? {b(cd)na/n = 0} ? {b(cd)nb/n = 0}

d) {acndnb|n = 1}

Answer is c) {a(cd)na|n = 0} ? {a(cd)nb/n = 0} ? {b(cd)na/n = 0} ? {b(cd)nb/n = 0}
Explanation : For explanation Join the discussion below

Q10. Which of the following regular expression identity is true?

a) r(*) = r*

b) (r*s*)* = (r + s)*

c) (r + s)* = r* + s*

d) r*s* = r* + s*

Answer is b) (r*s*)* = (r + s)*
Explanation : For explanation Join the discussion below

Q11. R1 and R2 are regular sets. Which of the following is not true?

a) R1 and R2 need not be regular

b) S* – R1 is regular

c) R1 ? R2 is regular

d) is regular

Answer is a) R1 and R2 need not be regular
Explanation : For explanation Join the discussion below

Q12. Which of the following does not represents the given language? Language: {0,01}

a) 0+01

b) {0} U {01}

c) {0} U {0}{1}

d) {0} ^ {01}

Answer is d) {0} ^ {01}
Explanation : The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.

Q13. Recursive languages are

a) a proper superset of CFL

b) always recognized by PDA

c) are also called type 0 languages

d) always recognized by FSA

Answer is a) a proper superset of CFL
Explanation : For explanation Join the discussion below

Q14. According to the given language, which among the following expressions does it corresponds to? Language L={xÏµ{0,1}|x is of length 4 or less}

a) (0+1+0+1+0+1+0+1)^4

b) (0+1)^4

c) (01)^4

d) (0+1+Îµ)^4

Explanation : The extended notation would be (0+1)4 but however, we may allow some or all the factors to be Îµ. Thus Îµ needs to be included in the given regular expression.

Q15. Which of the following strings is not generated by the following grammar? S ? SaSbS|e

a) aabb

b) abab

c) aababb

d) aaabb

Explanation : For explanation Join the discussion below

If you have any doubts join the discussion below ,our Moderator will reply to your Queries