In the name of ALLAH, the most beneficient, the most merciful

## Theory of Automata (CS402)

Multiple Choice Questions (MCQs)

## Objective Questions

### Question

A regular language can be:

1. irregular
2. infinite
3. non-deterministic
4. None of the given options

### Question

All possible combinations of strings of a language including null string is referred as:

1. Concatenation of a language with itself
2. Kleene star closure of a language
3. Multiplication of a language with itself
4. Addition of a language with itself

### Question

We cannot construct an NFA for the language of ______ defined over alphabet set {a,b}.

1. Even even
2. Odd
3. Palindromes
4. Integers

### Question

The minimum length of the strings(except null string) of a language that starts and ends in different letters will be

1. 1
2. 2
3. 3
4. 4

### Question

For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the ________.

1. Same
2. Different
3. R(S U T) is Greater
4. None of the given options

### Question

There ______ a language for which only FA can be built but not the RE.

1. is
2. cannot be
3. may be
4. may not be

### Question

The language {a ab aba bab} is ________.

1. Irregular
2. Regular
3. Recursive
4. None of the given options

### Question

If R is a regular language and L is some language, and L U R is a _______, then L must be a ________.

1. Regular language
2. Finite Automaton
3. NFA
4. Irregular language

### Question

In _______ there must be transition for all the letters of a string.

1. NFA
2. GTG
3. TG
4. FA

### Question

If we have a finite language and the number of states in the FA is n then the maximum number of letters in the each word of the language that will be accepted by the given FA will be:

1. 1
2. n-1
3. n+1
4. n

### Question

A string will be accepted by an NFA if there exist _______one successful path.

1. atmost
2. atleast
3. maximum
4. none of the given options

### Question

Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of

1. FA1 only
2. FA2 only
3. FA1 or FA2
4. FA1 and FA2

### Question

Decomposing a string into its valid units is referred as:

1. Decomposing
2. Splitting
3. Tokenizing
4. Dividing

### Question

FA and _______ are same except that _______ has unique symbol for each transition.

1. FA,TG
2. NFA,TG
3. NFA,FA
4. GTG,NFA