## Theory-of-Computation

Question 1 |

**head(s) - returns the first character of the string s****tails(s) - returns all but the first character of the string s****concat(sl, s2) - concatenates string s1 with s2.**

**concat(head(s), head(tail(tail(s))))**, where s is

**acbc**is

Ab | |

Ba | |

Ac | |

As |

s=acbc

head(s) = First character of the string of the string

tail(s) = All Except first character of the string

concat(head(s),head(tail(tail(s))))

concat(head(s),head(tail(tail(acbc))))

concat(head(s),head(tail(cbc)))

concat(head(s),head(bc))

concat(head(s),b)

concat(a,b)

ab

Question 2 |

A = {a ^{n} b^{n} | n = 1, 2, 3, …. } is a regular language | |

The set B, consisting of all strings made up of only a’s and b’s having an equal number of a’s and b’s defines a regular language | |

L(A * B) ∩ B gives the set A | |

None of the above |

**option(A)=False**

A={a

^{n}b

^{n}∣ n = 1,2,3,…} it is deterministic context free language(DCFL) not regular because it generates number of a's equal to number of b's. example: { ab, aabb, aaabbb, , , , a

^{n}b

^{n}}

**option(B) = False**

Equal number of a's and Equal number of b's is also Deterministic Context Free Language(DCFL) but not regular Language.

**option(C) = False**

L(A

^{∗}B) ∩ B gives the set B not set A

L(A*B)= L( { B + AB + AAB + AAAB + ......B} ) // B always there in A*B

L(A*B) ∩ B = B

Question 3 |

Union | |

Complementation | |

Kleene star | |

Product |

Question 4 |

Complements a given bit pattern | |

Finds 2’s complement of a given bit pattern | |

Increments a given bit pattern by 1 | |

Changes the sign bit |

Increments a given bit pattern by 1.

Table analysis for the above diagram

Question 5 |

Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is

2x – 1 | |

2x | |

2x + 1 | |

2 ^{x} |

**length x**, Number of productions in derivation is

**2x - 1**

In GNF to derive a string of terminals of

**length x**, Number of productions in derivation is

**x**

Question 6 |

S → ABCc ∣ bc

BA → AB

Bb → bb

Ab → ab

Aa → aa

Which of the following sentences can be derived by this grammar?

abc | |

aab | |

abcc | |

abbc |

S→ABc // now removed

Let see remaining productions

Bb → bb ( i.e. B→b)

Ab→ab (i.e.A→a)

Aa→aa (i.e. A→a)

∴S→ABc→abc

Question 7 |

S1 : Every context-sensitive language L is recursive

S2 : There exists a recursive language that is not context-sensitive

Which statements are true?

Only S1 is correct | |

Only S2 is correct | |

Both S1 and S2 are not correct | |

Both S1 and S2 are correct |

**S1 is True**= Context Sensitive Languages are the subset of recursive languages

**S2 is True**= Recursive languages are the superset of Context Sensitive Languages and it is not necessary that every Recursive language is Context Sensitive Languages.

Question 8 |

There is a unique minimal DFA for every regular language | |

Every NFA can be converted to an equivalent PDA | |

The complement of every context-free language is recursive | |

Every non-deterministic PDA can be converted to an equivalent deterministic PDA |

**TRUE**

(B) Every NFA can be converted to an equivalent PDA.

**TRUE**

Every Regular Language is CFL, so we can draw PDA for regular language also.

(C) Complement of every context-free language is recursive.

**TRUE**

CFL is a proper subset of recursive languages and recursive languages are closed under complement.

(D) =

**FALSE**

Non-deterministic PDA is more powerful then Deterministic PDA. So, DPDA cannot handle languages/grammars with ambiguity but NDPDA can handle ambiguity languages/grammar and DPDA is a proper subset of NDPA. so every DPDA can be converted to an equivalent NPDA(but reverse is not possible)

Question 9 |

(L + D)* | |

(L.D)* | |

L(L + D)* | |

L(L.D)* |

Question 10 |

Kleene Star L * of L | |

Intersection L ∩ P | |

Union L ∪ P | |

Set Difference |

Recursively enumerable languages are not closed under complement

Set difference= L−P can be written as L ∩ P

^{C}. where P

^{C}is complement of P so Set difference of these two language is not closed.

Question 11 |

Set of strings with 2 a’s and 2 b’s | |

Set of strings with 2 a’s 2 b’s followed by b | |

Set of strings with 2 a’s followed by b’s which is a multiple of 3 | |

Set of strings with even number of a’s followed by odd number of b’s |

^{∗}(bb)

^{∗}b contains Kleene star(*) where * means 0 or more occurrences

(aa)

^{∗}(bb)

^{∗}b = {b, , , ,, }

So, string "b" must accepted by r=(aa)∗(bb)∗b

So we can strike of option(A),option(B),option(C)

Question 12 |

**S → aSb | SS | ϵ**This grammar is

Not context-free, not linear | |

Not context-free, linear | |

Context-free, not linear | |

Context-free, linear |

**→**In left-linear or left regular grammars, in which all non-terminals in right hand sides are at the left ends.

**→**In right-linear or right regular grammars, in which all non-terminals in right hand sides are at the right ends.

**S→aSb the non terminal S appears in middle. so It is not linear grammar**

Context free grammar (CFG) are with each productions follows production rules A → B, where A single non-terminal and B is the set of terminal and non-terminal.

**In CFG non terminal can appear (in left, right or in between of RHS)**.

Question 13 |

S -> AB

A -> aAb|ϵ

B -> bB| b

{a ^{m}b^{n} | n>=m, m>0} | |

{a ^{m}b^{n} | n>=m, m>=0} | |

{a ^{m}b^{n} | n>m, m>0} | |

{a ^{m}b^{n} | n>m, m>=0} |

**{ a**

^{m}b^{n}∣ n>m, m≥0 }Which is Equal to option(D)

Question 14 |

_{1}be regular language, L

_{2}be a deterministic context free language and L

_{3}a recursively enumerable language, but not recursive.

Which one of the following statements is false?

L _{1} ∩ L_{2} is context-free | |

L _{3} ∩ L_{1} is recursive | |

L _{1} ∪ L_{2} is context-free | |

L _{1} ∩ L_{2} ∩ L_{3} is recursively enumerable |

L1 be regular language(RL)

L2 be a deterministic context free language (DCFL)

L3 a recursively enumerable language(REL) but not Recursive

option(A) =

**True**

L1∩L2 = RL ∩ DCFL = DCFL which is CFL

option(B) =

**False**

L3∩L1 = REL ∩ Regular = REL but may or may not RECURSIVE

option(C) =

**True**

L1∪L2 = RL ∪ DCFL= DCFL which is CFL

option(D) =

**True**

L1∩L2∩L3 = RL ∩ DCFL ∩ REL = Recursively enumerable language(REL)

Question 15 |

^{p}| p is a prime}.

Then which of the following is true?

It is not accepted by a Turing Machine | |

It is regular but not context-free | |

It is context-free but not regular | |

It is neither regular nor context-free but accepted by a Turing Machine |

^{p }| p is a prime}.

String generated by this language are L= { aaa,aaaaa,aaaaaaa,aaaaaaaaaaa,......},

and in L there is no definite pattern between the string .So this language is not regular language. and also not Context Free Language.

But this language is accepted by Turing machine using trial division algorithm

Question 16 |

Without rewinding capability and unidirectional tape movement | |

Rewinding capability and unidirectional tape movement | |

Without rewinding capability and bidirectional tape movement | |

Rewinding capability and bidirectional tape movement |

- Rewind is a procedure in which 1
^{st}element of input go to last element on tape and process it and come back to starting of input tape. - This is done by only Turing machine(TM's) because Turing machine can move in both direction so TM's is also called bidirectional.
- In Finite State Machine input move from left to right and one by one but It cannot be rewind. So FSM can be called as unidirectional tape movement

Question 17 |

(0*10*1)* | |

0*(10*10*)* | |

0*(10*1*)*0* | |

0*1(10*1)10* |

L Generating L is the set of all bit strings with even number of 1's.

**Option(A) : False**

This is not accepting string 110 (string 110 contains even number of 1's still not accepting)

**Option(C) : False**

This will accept some string which will not contain even number of 1's. example - 010, 1

**Option (D) : False**

This is not accepting string 11101 (String 11101 contains even number of 1's still not accepting)

Question 18 |

G = {S→ SS, S→ ab, S→ ba, S→ ∈}

I. G is ambiguous

II. G produces all strings with an equal number of a’s and b’s

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about?

I only | |

I and III only | |

II and III only | |

I, II and III |

**Statement I - True**

G is ambiguous because string ab has multiple derivation trees like

S → SS → abS → ab

S → ab.

**Example 2 :**string ababab has multiple derivation trees like

S → SS → abS → abSS → ababS → ababab

S → SS → SSS → abSS → ababS → ababab

**Statement II - False**

G does not produce all strings with equal no. of a's and b's example : string ‘aabb’ cannot be generated by G

**Statement III - True**

The given grammar G generates the language (ab+ba)

^{∗}which is Regular Language and therefore it is also DCFL

Question 19 |

Regular | |

Context-free | |

Context Sensitive | |

Recursive |

Question 20 |

All palindromes | |

All odd length palindromes | |

Strings that begin and end with the same symbol | |

All even length palindromes |

All this strings in the language L are odd length palindromes

Question 21 |

S → Aa

A → Ba

B → abc

Type 0 | |

Type 1 | |

Type 2 | |

Type 3 |

Question 22 |

Unified problem | |

Boolean function | |

Recursive problem | |

Decidable |

→Recursively Enumerable languages are also called as (Recognizable, partially decidable, semi-decidable , Turing-acceptable or Turing-recognizable)

**Note :**

→Recursive languages are also called decidable.

→a Turing machine that halts for every given input

Question 23 |

Which of the following sentences can be generated by

S -> aS | bA

A -> d | cA

bccdd | |

abbcca | |

abcabc | |

abcd |

S→abA

S→abcA

S→abcd

option(d) is correct answer

Question 24 |

q _{0}, q_{1}, q_{2} | |

[q _{0}, q_{1}], [q_{0}, q_{2}], [ ] | |

Q _{0}, [q_{1}, q_{2}] | |

[q _{0}, q_{1}], q_{2} |

→ From the diagram, q0 state is connected to q1 state and q1 state is connected to q2 state through epsilon transitions.

→ In additions to q2 state, q0 and q1 states are also the final states of the DFA.

Question 25 |

M x 2 ^{n} | |

2 ^{m+n} | |

2 ^{mn} | |

M+n |

^{x}states for a given input x

→ A word is of "n bits" and we have "m" such words. So, Total number of bits = m*n.

→Total number of sates required by FSM are 2

^{m*n}

Question 26 |

**((() ()) ())**for the following grammar?

S → SS

S → (S)

S → ε

10 | |

15 | |

12 | |

16 |

- s → (s)
- s → (ss)
- s → (s(s))
- s → (s())
- s → ((s)())
- s → ((ss)())
- s → (((s)s)())
- s → ((()s)())
- s → ((()(s))())
- s → ((()())())

Question 27 |

7 | |

9 | |

10 | |

11 |

then number of states = m*n

In the question Number 0's is divisible by 2 and Number of 1's is divisible by 5

So Total number of states = 2*5=10 states

Question 28 |

{1, 0}* {01} | |

{1, 0}* {1} | |

{1}{1, 0}* {1} | |

1*0* {0, 1} |

so only option(A) is correct

**Method 2 :**

**Option(A):**True

Ending with "01" {01,001,101,0001,0101,1001,1101,...} It accepts all strings.

**Option(B)**: False

Ending with "1". {1,01,11,001,...}. The strings "1", "11" are not accepted by Finite automata.

**Option(C):**False

Starting and ending with "1". {11,101,111,...}. The string "11" is not accepted by Finite automata.

**Option(D):**False

The string "0" is not accepted by Finite automata.

Question 29 |

Let denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in that are accepted by M is

0 | |

1 | |

2 | |

3 |

1) 01110110

2) 01110111

Question 30 |

S → AB

A → a

A → BaB

B → bbA

Which of the following statements is FALSE?

The length of every string produced by this grammar is even | |

No string produced by this grammar has three consecutive a’s | |

The length of substring produced by B is always odd | |

No string produced by this grammar has four consecutive b’s |

**option(A) : True**

length of every string produced by this grammar is even

Example : abba

**option(B) : True**

String produced by this grammar has a maximum of 2 consecutive a’s.

**option(C) : True**

**option(D) : False**

string produced by this grammar has 4 consecutive b’s

Example : abbbbaabba

S → AB

S → aB

S → abbA

S → abbBaB

S → abbbbAabbA

S → abbbbaabba

Question 31 |

It may halt and accept the input | |

It may halt by changing the input | |

It may halt and reject the input | |

It may never halt |

- It may halt and accept the input
- It may halt and reject the input
- It may never halt

Question 32 |

Have the same number of edges | |

Have the same number of states | |

Recognize the same set of tokens | |

Have the same number of states and edges |

- Having same number of edges and same number of states doesn’t mean that finite state machines are equivalent.
- Two finite state machines are said to be equivalent if they have the
**same input and output alphabets**and if, starting from their respective initial states, they produce the same output for any input string.

Question 33 |

Any string of odd number of a’s | |

Any string of odd number of b’s | |

Any string of even number of a’s and odd number of b’s | |

Any string of odd number of a’s and odd number of b’s |

**option(A) = False**

it not accepting string "aaa"

**option(B) = False**

it not accepting string "bbb"

**option(C) = False**

it not accepting string "aabb"

**option(D) = True**

The language accepted by given finite automata is

L = {ab, ba, aaab, ababab, bababa, ..............}

∴L is the language containing odd number of a’s and odd number of b’s.

Question 34 |

A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :

0 | |

1 | |

1 or more | |

2 or more |

→PDA behaves like a Turing machine when the number of auxiliary memory is 2 or more.

Question 35 |

Only context free grammar | |

Only regular grammar | |

Context free grammar or regular grammar | |

Only context sensitive grammar |

→Linear Bounded Automata = CSL , CFL , RL

→Push down automata = CFL , RL

→Finite Automata recognizes Regular Language(RL) only

Question 36 |

Consider the following two Grammars :

G1 : S → SbS|aG2 : S → aB|ab, A → GAB|a, B → ABb|b

Which of the following option is correct ?

Only G1 is ambiguous | |

Only G2 is ambiguous | |

Both G1 and G2 are ambiguous | |

Both G1 and G2 are not ambiguous |

→ Both G1 and G2 are ambiguous As both grammars have 2 derivations for same given string:

→ To generate string

**ababa**using G1 grammar has 2 different parse trees possible

**G1 : S → SbS | a**

**1)**

S → SbS

S →SbSbS

S →ababa

**2)**

S → SbS

S →SbSbS

S →ababa

→ To generate string

**aababbb**using G2 grammar has 2 different parse trees possible

**G2 : S → aB | ab, A→AB | a, B → ABb | b**

**1)**

S → aB

S →aABb

S →aABBb

S →aABABbb

S →aababbb

**2)**

S → aB

S → aABb

S → aAABbb

S → aABABbb

S → aababbb

Question 37 |

Context sensitive language can be recognized by a :

Finite state machine | |

Deterministic finite automata | |

Non-deterministic finite automata | |

Linear bounded automata |

**FA**= Regular Language = Regular Grammar

**PDA**= CFL = CFG

**LBA**= CSL = CSG

**TM**= REL = REG

So, Context sensitive language can be recognized by a

**LBA**

Question 38 |

The set A = { 0^{n} 1^{n} 2^{n} | n=1, 2, 3, ......... } is an example of a grammar that is :

Context sensitive | |

Context free | |

Regular | |

None of the above |

**Accepted**

0 0 0 1 1 1 2 2 2 2 =

**Not accepted**

→Given Grammar is number of 0’s followed by equal number of 1’s and then followed by equal number of 2’s.

→ This grammar is accepted by linear bound automata By using LBA which can move backward and upward and check the number of 0’s ,1's and 2's.

→This grammar is Context Sensitive language.

Question 39 |

Consider the following statements( ) :

S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.S2 : The problem of determining whether a Turing machine halts on any input is undecidable.

Which of the following options is correct ?

Both S1 and S2 are correct | |

Both S1 and S2 are not correct | |

Only S1 is correct | |

Only S2 is correct |

**Statement 1 = True**

It is "Equivalence problem" for the Recursive Enumerable languages and It is Undecidable. So, No Algorithm Exist.

**Statement 2 = True**

It is "Halting problem of TM". It is Undecidable and So, No Algorithm Exist.

Question 40 |

ab*b* | |

a*b* | |

b*b | |

b*ab* |

In option(A) not accepting "ba"

In option(B) not accepting "ba"

In option(C) three is no "a"

option(D) is correct all strings we can generate

Question 41 |

The set of all strings containing the substrings 11 | |

The set of all string containing at most two 1’s | |

The set of all strings containing at least two 1’s | |

The set of all strings that begins and ends with only 0. |

It may be typo in question

Consider this 110 all options are eliminated

for option(C) the questions should be like this

Set of all strings containing at least two 1’s = (0+1)*1(0+1)*1(0+1)*

Question 42 |

^{a}X

^{b}Y

^{a+b}| a,b >=1} is:

Regular | |

Context free but non regular | |

Context sensitive but non context free | |

Type 0 but non context sensitive |

^{a}X

^{b}Y

^{a+b}

W

^{a}X

^{b}Y

^{b}Y

^{a}

So first compare XY and then WY for this we require 1 stack so it is context free not regular

Question 43 |

(1) A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language

(2) The complement of a recursive language is recursive

(3) The complement of a context free language is context free

Only (1) | |

(1) and (2) | |

(1),(2) and (3) | |

(2) and (3) |

**Statement 1**: True

**Statement 2**: True

Recursive language are closed under complement

**Statement 3**: False

CFLs are not closed under complement

Question 44 |

(1) baaaba

(2) aabaaaa

(3) baaabaaaabaa

(4) baaabaaa

(1) | |

(2) | |

(3) | |

(4) |

Let S1 = ab , S2 = aa and S3 =baa

**baaaba**= baa ab a → It is not in L*-
**aabaaaa**= aa baa aa → S2 S3 S2 → It is in L* -
**baaabaaaabaa**= baa ab aa aa baa → S3 S1 S2 S2 S3 → It is in L* -
**baaabaaa**= baa ab aa a → It is not in L*

Correct option is (B)

Question 45 |

Finite state automaton | |

2-way linear bounded automata | |

Pushdown automata | |

Both (B) and (C) |

Question 46 |

Decidable | |

Undecidable | |

Interpretive | |

Non-deterministic |

→It means for a given input it will always Halt

Question 47 |

**L**= {x | for some y with |y|=2

_{1}^{|x|}, xy ∈ L and L is regular language}

**L**= { x | for some y such that |x| = |y|, xy∈L and L is regular language}

_{2}Which one of the following is correct?

Code:

Both L _{1} and L_{2} are regular languages | |

Both L _{1} and L_{2} are not regular languages | |

Only L _{1} is regular language | |

Only L _{2} is regular language |

_{1}and L

_{2}are regular languages

Contribute you explanation with diagrams and sent that image to academyera.com@gmail.com

Question 48 |

{a,b,ab,aa} | |

{a,b,ba,bb} | |

{a,b} | |

{aa,ab,ba,bb} |

={aa,ab,ba,bb}

**Note :**(a | b) means Either "a" or "b"

Question 49 |

Have same number of states | |

Have same number of edges | |

Have same number of states and edges | |

Recognized same set of tokens |

Question 50 |

Consider the following language:

L_{1}= { a

^{n+m}b

^{n}a

^{m }| n,m ≥ 0}

L

_{2}= { a

^{n+m }b

^{n+m}a

^{n+m}|n,m ≥ 0}

Which one of the following is correct?

Code:Only L _{1} is Context Free Language | |

Both L _{1} and L_{2} are not Context Free Language | |

Only L _{1} is Context Free Language | |

Both L _{1} and L_{2} are Context Free Language |

**L1 = { a**

Written as L1 = { a

^{n+m}b^{n}a^{m}| n,m ≥ 0}^{m}a

^{n }b

^{n}a

^{m}| n,m ≥ 0}

(push a′s into stack read b′s and pop a′s , when no b′s left on input and stack still contains a's, then keep reading a′s in input and pop a′s , when no a's left in input , and stack is empty, then accepted).

So,L1 can implemented using PDA . So L1 is CFL

**L2 = { a**

^{n+m}b^{n+m}a^{n+m}| n,m ≥ 0}Written as L2 = { a

^{x}b

^{x }a

^{x}| x>=0}

For every "b" we can pop a's came before "b" but for "a" which came after b we have nothing to pop in stack. So L2 can't be implemented using PDA

So L2 is not CFL

Question 51 |

∅
| |

{∈}
| |

a*
| |

{a, ∈} |

^{+}.

So, The complement of the language a

^{+ }is a

^{∗}− a

^{+ }= { ϵ }

Question 52 |

Neither L nor L' is RE | |

One of L and L' is RE but not recursive;The other is not RE | |

Both L and L' are RE but not recursive | |

Both L and L' are recursive |

**Option(A) is Possible**

if L is itself is NOT RE. Then L' will also not be RE.

**Option(B) is Possible**

Suppose there is a language such that Turing machine halts on the input. The given language is Recursive Enumerable but not recursive and its complement is NOT RE.

RE not closed under complement

**Option(C) is Not Possible**

If Both L and L' are Recursive enumerable then L must be recursive

**Option(D) is Possible**

Recursive closed under complement if L is recursive

Question 53 |

L1′ is recursive and L2′ is recursively enumerable | |

L1′ is recursive and L2′ is not recursively enumerable | |

L1′ and L2′ are recursively enumerable | |

L1′ is recursively enumerable and L2′ is recursive |

Recursive Enumerable Languages are not closed under complement

So option(B) is correct Answer

L1′ is recursive and L2′ is not recursively enumerable

If L1 is Recursive, then L1' is also Recursive because it closed under complement

IF L2 is RE then L2' is not RE because not closed under complement

Question 54 |

Consider the following problems:

(i) Whether a finite automaton halts on all inputs?(ii) Whether a given Context Free Language is Regular?

(iii) Whether a Turing Machine computes the product of two numbers?

Which one of the following is correct?

Code:Only (ii) and (iii) are undecidable problems | |

(i), (ii) and (iii) are undecidable problems | |

Only (i) and (ii) are undecidable problems | |

Only (i) and (iii) are undecidable problems |

- Whether a finite state automation halts on all inputs.
**Decidable** - Whether a given context-free language is regular.
**Undecidable**[ Regularity is decidable till DCFL class] - A Turing machine computes the products of two numbers,
**UNDECIDABLE**, Even though we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, Undecidable.

Question 55 |

- Does a given program ever produce an output?
- If L is a context-free language, then, is L' also context-free?
- If L is a regular language, then, is L' also regular?
- If L is a recursive language, then, is L' also recursive?

(a), (b), (c), (d) | |

(a), (b) | |

(b), (c), (d) | |

(c), (d) |

- This is Turing Machine Halting problem. So, it is
**undecidable.** - CFL are not closed under complement so complement of CFL may or may not be CFL so it is
**undecidable.** - Regular languages are closed under complementation. So, it is
**decidable** - Recursive languages are closed under complementation. So, it is
**decidable**

Question 56 |

If a language is context free it can always be accepted by a deterministic pushdown automaton | |

The union of two context free language is context free | |

The intersection of two context free language is context free | |

The complement of a context free language is context free |

**Option(A) = False**

A language can be CFL even if it is being accepted by Non-Deterministic PDA(N-PDA)

Example : { ww

^{r }: w ∈ Σ* and w

^{r}is reverse of w }

**Option(B) = True**

CFL are closed under Union, Concatenation and Kleen star

**Option(C) and Option(D) are False**

CFL are not closed under intersection and complementation

Question 57 |

Languages for palindrome and prime | |

Languages for palindrome and Even-Even | |

Language for prime and Even-Even | |

Language for palindrome and factorial |

Question 58 |

A*b* | |

(a | b)* | |

(ab) * | |

(a | b*) |

Set of all strings of a’s and b’s of any length including the null string. So L = { ε, a, b, aa , ab , bb , ba, aaa, bbbb, bababa…….}

Question 59 |

Non deterministic finite-state automata are equivalent to deterministic finite-state automata | |

Non deterministic PDA are equivalent to Deterministic PDA | |

Nondeterministic turing machines are equivalent to deterministic PDA | |

Multi tape Turing machines are equivalent to single tape Turing machines |

NTM and DTM are having same power

NFA and DFA have same power

**option(A) : True**

**option(B) : False**

power(NPDA) > DPDA.

**option(C) : False**

Power(TM) > NPDA > DPDA.

**option(D) : True**

Question 60 |

L1.L2 | |

L1 ∩ L2 | |

L1 ∩ R | |

L1 U L2 |

→L1 ∩ R is closed under CFL

**Note:**

Intersection of any language with Regular language is definitely closed

Question 61 |

^{(2*m)}c

^{(4*n)}d

^{n}b

^{m}| m,n>=0}. Find the best appropriate match to recognize L.

Finite automata | |

Pushdown automata | |

Non deterministic turing machine | |

Non deterministic PDA |

→ push a's and c's into stack and reading one d in input pop 4 c's at a time and while reading b pop 2 a's and when no d's left in input and stack is empty then it is accepted. For this we require 1 stack

→ you can implement using Push Down Automata because it have 1 stack

Question 62 |

Given problems is computable | |

Given problem is non computable | |

Given problem has finite state solution | |

Given problem is solved in polynomial time. |

→So, it is undecidable it means we don't have any algorithm to solve this problem

Question 63 |

(a+b) | |

(a+b)(a+b)* | |

(a+b)(a+b) | |

All of these |

→ Eliminate option(A) Which is only 1 character of length 1 either "a" or "b"

→ Eliminate option(C) Which is produces only 2 characters of length 2 like {aa,ab,bb,ba}

→ option(B) which produces strings of length which are greater then 2 also and it starts with either a or b followed by any number of a's or b's

Question 64 |

Regular language | |

Context free language | |

Context sensitive language | |

Recursive enumeration language |

Question 65 |

A={a ^{n}b^{n} |n= 0,1,2,3..} is regular language | |

Set B of all strings of equal number of a's and b's defines a regular language | |

L(A*B*) ∩ B gives the set A | |

None of these |

**False**

A={a

^{n}b

^{n} |n= 0,1,2,3..} = DCFL not Regular

option(B) =

**False**

Equal number of a's and b's which is again DCFL not regular

option(D) =

**False**

L(A*B*) ∩ B gives the set B not set A

Question 66 |

Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions.

Consider the following:(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)

(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)

Choose the correct answer from the code given below :

**Code :**

Only (i) is correct | |

Both (i) and (ii) are correct | |

Only (ii) is correct | |

Neither (i) nor (ii) is correct |

So, L(r) is superset among L(s) and L(t)

L(s) is propersubset of L(r) and L(s) is propersubset of L(t)

∴ L(r) ⊇ L(s) ⊇ L(t)

Given key is 1 but it should be 4

Question 67 |

Union | |

Concatenation | |

Kleene's closure | |

All of these |

→Union

→Concatenation

→Kleene's closure

Question 68 |

Consider the language L given by

L = {2^{nk}| k>0, and n is non-negative integer number}

The minimum number of states of finite automaton which accept the language L is

N | |

N+1 | |

2 ^{n} | |

N(n+1)/2 |

Question 69 |

Which of the following problem is decidable for recursive language (L) ?

Is L = ф ? | |

Is w∈L, where w is a string ? | |

Is L = R, where R is given regular set ? | |

Is L = Σ* ? |

**Emptiness of Recursive Language**→ undecidable**Membership problem of Recursive language**→ Decidable**L=R**→ Undecidable**L(G) = Σ***Completeness problem or Totality problem of RL → Undecidable

Question 70 |

Consider R to be any regular language and L_{1 }, L_{2} be any two context-free languages

L _{1 } - R is context free | |

L _{1}' is context free | |

L _{1 }∩ L_{2 } is context free |

- CFL are closed under union and difference with regular language.
- Where CFL are not closed under intersection and complementation a
- Complement of CFL is recursive language .
- Regular Language is closed under complementation
- CFL is closed under Intersection with Regular Language

**option(A) : False**

Context free language are closed under union but not complementation

L1∪L2 is CFL but complement(L1∪L2) is not CFL always

**option(B) : True**

L1−R = L1 ∩ R' =L1 ∩ R Always True

Regular language are closed under complementation and intersection of CFG and Regular is CFG.

**option(C) : False**

CFL are not closed under complementation

**option(D) : False**

CFL are not closed under intersection

Question 71 |

No | |

Yes | |

Sometimes | |

Depends on NFA |

→You can convert any NFA to DFA So NFA and DFA are both equivalent in power

Question 72 |

FSA cannot remember arbitrarily large amount of information | |

FSA cannot deterministically fix the midpoint | |

Even if the mid-Point is known an FSA cannot find whether the second half of the matches the first half | |

All of the above |

**FSA has finite memory**

→FSA cannot deterministically fix the midpoint because

**not able to find midpoint in palindrome.**

→

**FSA has finite memory**So, Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half.

Question 73 |

L1-L2 is not context free | |

L1 intersection L2 is context free | |

~L1 is context free | |

Both (A) and (C) |

**option(A) : False**

L1-L2 can be written as L1 ∩ L2' = CSL

Regular languages are closed under complement

CSL are closed under intersection with regular

According to Chomsky hierarchy every CFL is CSL. So L1 ∩ L2' = CLF also

**option(B) : True**

L1 ∩ L2 = CFL

CSL are closed under intersection with regular languages

So L1 ∩ L2 = CSL

According to Chomsky hierarchy every CFL is CSL. L1 ∩ L2 = CLF also

**option(C) : False**

Every CSL compliment is not always CFL

CSL is closed under compliment

CFL is not closed under complement. So, complement of CFL may or may not be a CFL.

Question 74 |

Turing machine is a simple mathematical model of general purpose computer | |

Turing machine is more powerful than finite automata | |

Turing Machine can be simulated by a general purpose computer | |

All of these |

**- TRUE**

Turing machine is more powerful than finite automata

**- TRUE**

Turing Machine can be simulated by a general purpose computer

**- TRUE**

All options are true none of the option is wrong

Question 75 |

M1 and M2 has the same number of states | |

M1 and M2 accepts the same language i.e L(M1)=L(M2) | |

M1 and M2 has the same number of final states | |

None of the above |

→Two DFA's M1 and M2 over the same alphabet are equivalent if they accept the same language

i.e.

**L(M1)=L(M2)**

Question 76 |

Strings not starting with 11 | |

Strings of odd length | |

Strings starting with 00 | |

Strings of even length |

**(00+01+10)(0+1)***

Given regular Expression can generate strings with any length(Even length string or odd Length sting) but string must start with 00 or 01 or 10

So Eliminate option(B),option(D) and option(C)

**option(A) :**correct

String starts with 00 or 01 or 10 not with 11

Question 77 |

R1 ∩ R2 is not regular | |

R1 ∪ R2 is not regular | |

Σ * – R1 is regular | |

R1 * is not regular |

- Intersection (∩)
- Union (∪)
- Complement
- Kleene Closure (*)

**Σ* – R1 = Σ* ∩ R1’**= It is regular language because it is closed under complement

Question 78 |

(i) In NDFA, the transition function δ: Q × Σ → 2

^{Q}

(ii) NDFA does not permit empty string transitions

(i) False (ii) False | |

(i) True (ii) False | |

(i) False (ii) True | |

(i) True (ii) True |

Question 79 |

Language L={x ɛ {0,1} | x is of length or less}

(0+1+0+1+0+1+0+1) ^{4} | |

(0+1) ^{4} | |

(01) ^{4} | |

(0+1+ɛ) ^{4} |

**(0+1+ε)**

^{4}=ε+(0+1)

^{1}+(0+1)

^{2}+(0+1)

^{3}+(0+1)

^{4}

=(ε+0+1)

^{4}

Question 80 |

_{1}, W

_{2 }

**ɛ**L(G) such that |W

_{1}|=|W

_{2}| then which of the following statement is TRUE ?

Any derivation of W _{1} has exactly the same number of steps as any derivation of W_{2} | |

Different derivation have different length | |

Some derivation of W _{1} may be shorter the derivation of W_{2} | |

None of the options |

G be a CFG Grammar

W1 and W2 are 2 strings of same Length

**Example :**

X → Yd | dd

Y → a

W1= dd and W2=ad

∴ |W1| = |W2|

W1 needs 1 derivation X → dd

W2 needs 2 derivation X → Y → ad

**Note :**They clearly specified in the option some derivations may be

Question 81 |

Set of strings with either a or one or more occurences of b followed by c. | |

(b*c+a) | |

Set of strings with either a or zero or more occurence of b followed by c | |

Both (B) and (C) |

→In option(A) they not specified about zero occurrence

Question 82 |

P1: The language generated by some CFG contains any words of length less than some given number n.

P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements

P3: Any given CFG is ambiguous or not

P4: For any given CFG G, to determine whether ɛ belongs to L(G)

P2 only | |

P1 and P2 only | |

P2 and P3 only | |

P3 only |

**Decidable**

→ P2 = CFL intersection with Regular is

**Decidable.**

→ P3 = No algorithms to check that CFG is ambiguous or not so it is

**Undecidable**

→ P4= we can determine

**ε**is in language or not in the language . If

**Start Symbol**itself contain

**ε**then we can say it belongs to language is

**Decidable**

So only P3 is is Undecidable

Question 83 |

Set difference | |

Complement | |

Both (A) and (B) | |

None of the options |

**Proof :**A

_{tm}is Recursively Enumerable but complement(A

_{tm}) is not Recursively Enumerable

→Recursively Enumerable languages are not closed under set difference

Question 84 |

Any string containing '1' as substring | |

Any string containing '01' as substring | |

Any string containing '011' as substring | |

All string containing '001' as substring |

→ Σ* 001 Σ* = All string containing '001' as substring

Question 85 |

Unambiguous CFG | |

Ambiguous CFG | |

Not a CFG | |

Deterministic CFG |

**Parse Tree 1 = ab**

S / \ S S / | \ | a s b € | €

**Parse Tree 2 = ab**

S / \ S S / / | \ € a s b | €

Question 86 |

Regular | |

Context free but not regular | |

Recursive but not necessarily context free | |

Recursively enumerable but not necessarily recursive |

→ Given Language is Recursive Language

→If the string is in lexicographic order then Turing Machine will accept the string and halt in the final state. But, if the string is not lexicographic order then Turing Machine will reject the string and halt in non-final state.

→We can not construct PDA for language L. So, the given language is not context free.

→ Given L is Recursive but not necessarily Context Free

Question 87 |

i. Union

ii. Intersection

iii. complement

iv. Concatenation

v. star closure

I only | |

Both i,iv | |

I,ii,iv and v | |

All of the options |

→ RE are not closed under complement

→ RE are closed under Union, Intersection, Concatenation, Star Closure.

Question 88 |

R1*r2* | |

(r1r2)* | |

R1*r2*+r1r2 | |

(r1*r2*)* |

(a+b)* ≈ (a*b*)* ≈ (a*+b*)* ≈ (a+b*)* ≈ (a*+b)* ≈ (b*a+a*b)*

Question 89 |

S1: The power of a multi tape Turing machine is greater than the power of a single tape turing machine

S2: Every non deterministic Turing machine has an equivalent deterministic Turing machine

S1 | |

S2 | |

Both S1 and S2 | |

None of the options |

→Non Deterministic Turing Machine and Deterministic Turing Machine are equivalent in power.

only s2 is true

Question 90 |

It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string) | |

It is the finite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string) | |

It is the finite set of all possible strings of all possible lengths over Σ(input set) | |

It is the infinite set of all possible strings of all possible lengths over Σ(input set) |

Question 91 |

Mealy and Moore machine are language acceptors

Finite state automata is language translator

NPDA is more powerful than DPDA

Mealy machine is more powerful than Moore machine

Mealy and moore machine are language acceptors | |

Finite state automata is language translator | |

NPDA is more powerful than DPDA | |

Mealy machine is more powerful than moore machine |

→NPDA is more powerful than DPDA

Power(NPDA) > Power(PDA)

→NFA and DFA are both are equivalent in power

→Mealy and Moore machine have equal power.

→Mealy and Moore machines are not language acceptors. They produce output based on input and/or state using actions. They are categorized under Transducers. Language acceptors are separate classification under FSM.

Question 92 |

(00+(11)*0) | |

1(0+1)*101 | |

(10)*(01)*(00+11)* | |

110*(0+1) | |

Both option(A) and option(C) |

→ option(B) you can generate 1101

→In option(c) after 11, we can't have 01 and so 1101 can not generated 1101.

→ option(D) you can generate 1101

So option(A) and option(C) are both are correct

Question 93 |

N(n+1) | |

N ^{2} +1 | |

N ^{2} -1 | |

N(n+1)/2 |

→ If the length of the string is ‘n’ then the Total Number of Table Entry in CYK algorithm is (n(n+1))/2

→ CYK algorithm takes O(n) time to compute each entry in table so whole table takes O(n)

^{3}time in worst case

Question 94 |

Deterministic Context free language are closed under complement

Deterministic Context free language are not closed under union

Deterministic Context free language are closed under intersection with regular set

Deterministic Context free language are closed under complement | |

Deterministic Context free language are not closed under union | |

Deterministic Context free language are closed under intersection with regular set | |

All of the options |

**- True**

→Deterministic Context free language are not closed under union

**- True**

→Deterministic Context free language are closed under intersection with regular set

**- True**

Question 95 |

PDA | |

TM | |

LBA | |

None of the options |

→Deterministic Turing machine and Non-Deterministic Turing machine are equivalent in power

→NFA and DFA also have same equivalent in power

Question 96 |

L1: Set of languages accepted by NFA

L2: Set of languages accepted by DFA

L3: Set of languages accepted by DPDA

L4: Set of languages accepted by NPDA

L5: Set of recursive languages

L6. Set of recursively enumerable languages?

L1,L2⊂ L3⊂ L4⊂ L5⊂ L6 | |

L1⊂L2⊂ L3 ⊂L4⊂ L5 ⊂L6 | |

L2⊂L1⊂ L3 ⊂L4⊂ L5⊂ L6 | |

L1⊂L2⊂ L3⊂ L4⊂ L6⊂ L5 |

Question 97 |

Pushdown automata | |

Turing machine | |

Linear Bounded Automata | |

None of the options |

Question 98 |

i.((01)*(10)*)*

ii.(10+01)*

iii.(01)*+(11)*

iv.(0*+(11)*+0*)*

I and ii | |

Ii and iii | |

Iii and iv | |

Iv and i |

(a*b*)* = (a+b)* which is (01+10)*.

Both (i) and (ii) have same expression

Question 99 |

L={ x

^{n} y

^{n} , n>=1 }

**i.**E → xEy | xy

**ii.**xy | x

^{+} xyy

^{ +}

**iii.**x

^{+} y

^{+}

I only | |

I and ii only | |

Ii and iii only | |

Ii only |

^{n} y

^{n} , such that n>=1 }

when n=1, string would be "xy"

when n=2, string would be "xxyy"

when n=3, string would be "xxxyyy"

So given language is Equal number of x's followed by y's

**Statement (I) :**In Statement (I) we have restriction over the number of a's and b's both being equal.

**Statement (II) and Statement (III)**There is no restriction over the number of a's and b's . You can have any number of x and y.

Question 100 |

A language is a subset of Σ* for some alphabet Σ. If a language takes all possible strings of length 2 over Σ = {a,b}, then, which of the below is correct?

L = {ab,bb,ba} | |

L = {aa,ab,ba,bb} | |

L = {ab,bb,aa} | |

L = {ab,ba,aa} |

option(B) contains all 4 strings

Question 101 |

NFA | |

DFA | |

NFA-ɛ / NFA-l | |

All of the above |

An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol. It may appear in almost all kinds of nondeterministic automaton in formal language theory, in particular:

- Nondeterministic Turing machine
- Nondeterministic pushdown automaton
- Nondeterministic finite automaton

Question 102 |

Making starting state as final state | |

Make final as a starting state | |

Make final states non-final and non final as final | |

None of the options |

→The language accepted by the complemented DFA L2 is the complement of the language L1.

Question 103 |

Union | |

Dot | |

Kleene | |

None of the options |

→Concatenation means Two operands(or strings) are said to be joining together

**Example :**AB = A•B = {xy : x ∈A & y ∈B}.

Question 104 |

Mealy and Moore machine are language acceptors

Finite state automata is language translator

NPDA is more powerful than DPDA

Mealy machine is more powerful than Moore machine

Mealy and moore machine are language acceptors | |

Finite state automata is language translator | |

NPDA is more powerful than DPDA | |

Mealy machine is more powerful than moore machine |

Question 105 |

Regular | |

Non regular | |

Recursive | |

Non Recursive |

Question 106 |

Q*P | |

QP* | |

Q*P* | |

(P*Q*)* |

**Arden’s Theorem**

→Arden’s Theorem is used to convert a given DFA to its Regular Expression.

→Arden’s Theorem can be used to find a regular expression for both DFA and NFA.

→Let P and Q be two regular expressions over ∑. If P does not contain a null string ∈, then

**R = Q + RP**has a unique solution i.e. R = QP*

Question 107 |

Type 0 | |

Type 1 | |

Type 2 | |

Type 3 |

Question 108 |

{0,1,01,ɛ} | |

{0,1,ɛ} | |

{0,1,01,11,00,10,ɛ} | |

{0,1} |

Question 109 |

DFA>NFA | |

NFA>DFA | |

Equals | |

Can't be said |

→BY default All DFA are NFA. You can convert given NFA to DFA so both NFA and DFA are Equivalent in power

Question 110 |

16 | |

26 | |

32 | |

64 |

→ Number of DFA’s = 2

^{n}* n

^{(2*n)}= 2

^{2}* 2

^{(2*2)}= 64

Question 111 |

Π | |

∅ | |

A | |

B |

→Power set of {Π } = {{},{Π}}

→Power set of {}= {Π}

Question 112 |

1 | |

0 | |

2 | |

None of the options |

→ Pushdown Automata is a finite automata with extra memory called stack = 1 stack

Question 113 |

(0+0+1)(0+0+1) | |

(0+0+0)(0+1+1) | |

(1+0+0)(1+1+1) | |

(0+1+0)(1+0+1) |

→ In option(B) : product with 0 gives results also 0

=(0+0+0)(0+1+1)

=(0+1+1) gives results as 0 or 1

=(0+0+0) gives results as 0

Question 114 |

Recursive | |

Recursively enumerable | |

NP-Hard | |

None of the above |

→ Only difference between Recursively Enumerable and Recursive Language is

- Recursively Enumerable may or may not Halt
- Recursive Language is always Halt

Question 115 |

The pigeonhole principle | |

The divide and conquer technique | |

Recursion | |

Iteration |

→ Finite state automaton can assume only a finite number of states and because there are infinitely many input sequences, by the pigeonhole principle, there must be at least one state to which the automaton returns over and over again. This is an essential feature of the automaton.

Question 116 |

A DFA can be expressed as a 5 tuple(Q, Σ, δ, q_{0}, F), where δ is the transition function defined as ___?

Δ: Σ → Q | |

Δ: Q x Q → Σ | |

Δ: Q → Q | |

Δ: Q x Σ → Q |

Question 117 |

If r and s are regular expression representing the languages L(r) and L(s), respectively, then which of the following is FALSE?

(r)|(s) is a regular expression representing L(r)UL(s) | |

(r)|(s) is a regular expression representing (L(r))* or (L(s))* | |

(r)* is a regular expression representing (L(r))* | |

(r)(s) is regular expression representing L(r)L(s) |

**option(A)**: union

(r)|(s) is a regular expression representing L(r) U L(s)

**option(C)**: Kleene closure

(r)* is a regular expression representing (L(r))* ; ( L(r1*)=(L(r1))* )

**option(D)**: Concatenation

(r)(s) is regular expression representing L(r)L(s)

Question 118 |

L={ x

^{ n} y

^{ n} , n>=1 }

i. E → xEy | xy

ii. xy | x

^{+}xyy

^{ +}

iii. x

^{ +} y

^{ +}

I only | |

I and ii only | |

Ii and iii only | |

Ii only |

Question 119 |

R → XRX|S S → aTb|bTa T → XTX|X|ϵ X → a|bThe strings which are not in L(G) are:

Ab,ba,aab | |

Abb,aabab | |

A,b,aa | |

A,b,ϵ |

→3 examples of strings not in L(G) : (a, b, aa)

Given grammar starts with R → XRX | S you can't generate only a or only b or aa

Question 120 |

0*1 ^{+} 0*1* | |

0*1*0 ^{+} 1* | |

0*1*0*1 ^{+} | |

0 ^{+}1*0*1* |

→ Any non-negative Even number Represented in binary form then LSB bit must be 0

→ In option(C) 0*1*0*1

^{+}(

**+**indicate must have 1 in LSB.) So, this Language won't contain any even numbers

Question 121 |

**(i)**The grammar

**S → SS | a**is ambiguous (where

**S**is the start symbol).

**(ii)**The grammar

**S → 0S1 | 01S | ϵ**is ambiguous (the special symbol

**ϵ**represents the empty string and S is the start symbol).

**(iii)**The grammar (where

**S**is the start symbol).

**S → T/U**

**T → x S y | xy | ϵ**

**U → yT**

generates a language consisting of the string

**yxxyy.**

Only (i) and (ii) are TRUE | |

Only (i) and (iii) are TRUE | |

Only (ii) and (iii) are TRUE | |

All of (i), (ii) and (iii) are TRUE |

**option(A) :**S→SS | a

This is ambiguous grammar because generates more then 1 parse tree for same string "aaa"

**Derivation 1 :**

S→SS→Sa→SSa→Saa→aaa

**Derivation 2 :**

S→SS→aS→aSS→aaS→aaa

**option(B) :**S → 0S1 | 01S | ϵ

This is ambiguous grammar because generates more then 1 parse tree for same string "01"

**Derivation 1 :**

S→0S1→01

**Derivation 2 :**

S→01S→01

**option(C) :**yxxyy

S → U

U → yT

yT → yxSy

yxSy → yxTy

yxTy → yxxyy

Question 122 |

^{+}[3 – 5]* [xyz] ?

I. p443y

II. p6y

III. 3xyz

IV. p35z

V. p353535x

VI. ppp5

I, III and VI only | |

IV, V and VI only | |

II, IV and V only | |

I, IV and V only |

p

^{+}[3-5]*[xyz] = p

^{+}(3+4+5)*(x+y+z)

All strings must start with character p followed by 3 or 4 or 5 either 0 occurrence or more occurrence and must end with either x or y or z

**I.**p443y = Valid

**Il.**p6y = Invalid because 6 cannot used we can use only among (3,4,5).

**III.**3xyz = Invalid Strings must start with p.

**IV.**p35z = Valid

**V.**p353535x =Valid

**Vl.**ppp5 = Invalid Strings must end with x or y or z.

Question 123 |

^{+} 1

^{+} | 2

^{+} 3

^{+} )*, where | is an alternation character and {+, *} are quantification characters, is:

08 | |

09 | |

10 | |

12 |

Regular expression (0

^{+} 1

^{+} | 2

^{+} 3

^{+} )*

Total Possible strings of length 4 are :

0001, 0111, 0011, 0101, 0123, 2323, 2333, 2223, 2233, 2301.

Total 10 strings are possible.

**With 01 =**0111, 0011, 0001, 0101

**With 23 =**2333, 2233, 2223, 2323

**Using both 01 and 23**= 0123, 2301

Question 124 |

The grammar S→aS|aSbS|∈, where S is the only non-terminal symbol, and ∈ is the null string, is ambiguous. | |

An unambiguous grammar has same leftmost and rightmost derivation. | |

An ambiguous grammar can never be LR(k) for any k. | |

Recursive descent parser is a top-down parser. |

**option(A) : True**

Consider the string "aab" having more then 1 parse tree

**Derivation 1 :**

S−>aS

S−>aaSbS

S−>aaϵbS

S−>aabϵ

S−>aab

**Derivation 2 :**

S−>aSbS

S−>aaSbS

S−>aaϵbS

S−>aabϵ

S−>aab

**option(B) : False**

An Unambiguous grammars have different Left Most Derivation and Right Most Derivation

**option(C) : True**

**option(D) : True**

Question 125 |

(0|∈)1 + 2* (3|∈),

where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is :

08 | |

10 | |

11 | |

12 |

^{+}2* (3 | ∈)

**Possible strings of length 4 are :**

0122, 0123, 1123, 0112, 0113, 1113, 0111, 1222, 1123, 1111, 1223, 1112;

Total 12 strings are possible

Question 126 |

Context free grammar | |

Context sensitive grammar | |

Unrestricted grammar | |

Phrase grammar |

**α → β**

In CFG Left hand side of production can have only one variable.

|α | = 1.

Their is no restriction on β

**Example**

S → AB

A → a

B → b

Question 127 |

(i) Intersection

(ii) Union

(iii) Complementation

(iv) Kleene Star

then

(i) and (iv) | |

(i) and (iii) | |

(ii) and (iv) | |

(ii) and (iii) |

Context free languages are not closed under intersection and complement

Question 128 |

**S → d/bA**

**A → d/ccA**

Bccddd | |

Aabccd | |

Ababccd | |

Abbbd | |

None |

→ option(A) is also not correct because it is generating string "bccccd"

S → bA

S → bccA

S → bccccA

S → bccccd

None of the option is correct

Question 129 |

{a} | |

{ε, a, b} | |

{a, b} | |

None of these |

→Either "a" or "b"

Question 130 |

Power of deterministic automata is equivalent to power of non-deterministic automata. | |

Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata. | |

Power of deterministic turing machine is equivalent to power of non-deterministic turing machine. | |

All the above |

**option(A) :**Power of deterministic automata is equivalent to power of non-deterministic automata.

**- True**

**option(B) :**Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.

**- False**

**-**NPDA is more powerful then DPDA

**option(C) :**Power of deterministic Turing machine is equivalent to power of non-deterministic Turing machine.

**- True**

Question 131 |

L = { wwR ǀ wε{0,1}* } | |

L = { a ^{n} b^{ n} ǀ n≥0 } | |

L = { ww ǀ wε{0,1}* } | |

L = { a ^{n} b^{ m} c^{ m} d^{ n} ǀ n,m ≥0 } |

**option(A)**

L = { ww

^{R}ǀ wε{0,1}* } -

**CFL**

we can find mid-point in the expression even in a non-deterministic way

**option(B)**

L = { a

^{n} b

^{ n} ǀ n≥0 } -

**CFL**

push a’s and then we can pop a’s for each occurrence of b.

**option(C)**

L = { ww ǀ wε{0,1}* } -

**CSL**

we can't implement using PDA

One might think to draw a non-deterministic push down automaton, but it will not help as first symbol will be at bottom of the stack and when the second W starts, we will not be able to compare it with the bottom of stack.

**option(D)**

L = { a

^{n} b

^{ m} c

^{ m} d

^{ n} ǀ n,m ≥0 } -

**CFL**

we can implement using PDA push a's and b's on seeing one c pop one b in stack follow the same for d on seeing d pop a. finally input became empty and stack became empty then accepted

Question 132 |

Regular | |

Context - Sensitive | |

Context free | |

None of these |

→Phrase Structure Grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars.

→The most general one in the given options is context sensitive because it covers the context free grammars.

Question 133 |

Build the symbol table | |

Construct the machine code | |

Separate mnemonic opcode and operand fields. | |

None of these |

Question 134 |

S →AB/AS, A→a/aA, B→b

aa*b + | |

aa*b | |

(ab)* | |

a(ab)* |

**option(B) : aa*b**

starts with "a" followed by number of a's either 0 occurrence or more occurrence and ends with "b"

S → AB→

**ab**

or

S→AB→aAb→

**aab**

or

S→AB→aAb→aaAb→

**aaab**

or

S→AS→AAS→AAAS -----so on

**aa*b**

Question 135 |

Regular | |

Context-sensitive | |

Context free | |

Syntax tree |

Question 136 |

S → 0A

A → 1A/0A/1

01100 | |

00101 | |

10011 | |

11111 |

S → 00A

S → 001A

S → 0010A

S → 00101

option(B) is correct

Question 137 |

**S → aB | bA**

**A → a | as | bAA**

**B → b | bs | aBB**

will generate

Odd numbers of a’s and odd numbers of b’s | |

Even numbers of a’s and even numbers of b’s | |

Equal numbers of a’s and b’s | |

Different numbers of a’s and b’s |

**option(A) : False**

it can generate "aabb" which is even number of a's and b's

S→aB

B→aaBB

B→aabb

**option(A) : False**

it can generate "ab" which is odd number of a's and b's

S→aB

B→ab

**option(D) : False**

It always generate equal number a's and b's

Question 138 |

L

_{1} = { x | for some y with | y| = 2

^{|x|}, xy∈ L and L is regular language}

L

_{2} = { x | for some y such that |x| = |y|, xy∈ L and L is regular language}

Which one of the following is correct?

Both L _{1} and L_{ 2} are regular languages | |

Both L _{1} and L _{ 2} are not regular languages | |

Only L _{1} is regular language | |

Only L _{ 2} is regular language |

Question 139 |

10 | |

45 | |

56 | |

55 |

**a d e f b g h n m p ;**

All are distinct

So N=10

Total Number of substrings can be found using the below formula :

**N(N+1)/2 + 1**( 1 is for epsilon)

=10(10+1)/2 +1

=10(11)/2+1

∴

**Number of substrings**= 56

Question 140 |

**L**

_{1} = { a^{ n+m}b^{ n}a^{ m}| n, m ≥ 0 }**L**

_{2} = { a^{ n+m}b^{ n+m}a^{ n+m}|n, m ≥ 0 }Which one of the following is correct?

Only L _{ 1} is Context Free Language | |

Both L _{1} and L_{ 2} are not Context Free Language | |

Only L _{1} is Context Free Language | |

Both L _{ 1} and L_{ 2} are Context Free Language |

Question 141 |

(i) Whether a finite automaton halts on all inputs?

(ii) Whether a given Context Free Language is Regular?

(iii) Whether a Turing Machine computes the product of two numbers?

Which one of the following is correct?

Only (ii) and (iii) are undecidable problems | |

(i), (ii) and (iii) are undecidable problems | |

Only (i) and (ii) are undecidable problems | |

Only (i) and (iii) are undecidable problems |

Question 142 |

**L = { a**is

^{n}b^{m}c^{k}| k = | n – m |, n ≥ 0, m ≥ 0, k ≥ 0 }S → S _{1}S_{3}, S_{1} → aS_{1}c | S_{2}| λ,S_{2} → aS_{2}b|λ, S_{3 }→ aS_{3}b| S_{4} | λ,S_{4} → bS_{4}c|λ | |

S → S _{1}S_{3}, S_{1}→ aS_{1}S_{2}c | λ,S_{2} → aS_{2}b|λ, S_{3} → aS_{3}b| S_{4} |λ,S_{4} → bS_{4}c|λ | |

S → S _{1}|S_{2}, S_{1}→ aS_{1}S_{2}c | λ,S_{2} → aS_{2}b | λ, S_{3} → aS_{3}b | S_{4} |λ,S_{4} → bS_{4}c|λ | |

S → S _{1} | S_{3}, S_{1}→ aS_{1}c|S_{2} | λ,S_{2} → aS_{2}b | λ, S_{3} → a S_{3}b| S_{4} | λ,S_{4} → bS_{4}c | λ |

Question 143 |

Consider the following:

(i) L(s) ⊆ L(r) and L(s) ⊆ L(t)

(ii). L(r) ⊆ L(s) and L(s) ⊆ L(t)

Only (i) is correct | |

Both (i) and (ii) are correct | |

Only (ii) is correct | |

Neither (i) nor (ii) is correct |

Question 144 |

L = { 2

^{nk}| k > 0 , and n is non − negative integer number }

The minimum number of states of finite automaton which accept the language L is

N | |

N+1 | |

2 ^{n} | |

N (n + 1 )/2 |

Question 145 |

Is L = ф ? | |

Is w∈L, where w is a string ? | |

Is L=R, where R is given regular set ? | |

Is L = Σ* ? |

**Emptiness of Recursive Language**→ undecidable**Membership problem of Recursive language**→ Decidable**L=R**→ Undecidable**L(G) = Σ***Completeness problem or Totality problem of RL → Undecidable

Question 146 |

_{1} , L

_{2} be any two context-free languages Which one of the following is correct ?

L _{1 } - R is context free | |

L _{1}' is context free | |

L _{1 }∩ L_{2 } is context free |

Question 147 |

^{n}| n≥4 } is

3 | |

4 | |

5 | |

6 |

Question 148 |

(1 + 010)* | |

(01 + 10)* | |

(1 + 010)* (0 + λ) | |

(1 + 01)* (0 + λ) |

**option (a) : False**

We can generate 010010 which contains pair of consecutive zeros

**option (b) : False**

We can generate 1001 which contains pair of consecutive zeros

**option (c) : False**

We can generate 0100 which contains pair of consecutive zeros

**option (D) : True**

Not contains any pair of consecutive zeros

Question 149 |

**L1 = {a**

^{n}b^{l}a^{k}| n + l + k>5 }**L2 = {a**

^{n }b^{l}a^{k}| n>5, l >3, k≤ l }Which of the following is true ?

L _{1} is regular language and L_{2} is not regular language. | |

Both L _{1} and L_{2} are regular languages. | |

Both L _{1} and L_{2} are not regular languages. | |

L _{1} is not regular language and L_{2} is regular language |

→To implement L2 we need stack to remember the value of l (number of b's) so that it can be compared with k. so it not regular language

∴

**L1 is regular language and L2 is not regular language**

Question 150 |

^{n}b

^{m}c

^{n+m}| m≥0, n≥0} is

S → aSc | S _{1} ; S_{1} → bS_{1}c | λ | |

S → aSc | S _{1}| λ ; S_{1} → bS_{1}c | |

S → aSc | S _{1}| λ ; S_{1} → bS_{1}c| λ | |

S → aSc | λ ; S _{1} → bS_{1}c| λ| |

**option (A) : False**

It is n > 0 and m >0 in every condition so m=0 is not satisfied

**option (B) : False**

It does not have any stopping condition. There is no way to stop the cycle S1→bS1c

**option (C) : True**

It can generate all strings by the language L

**option (D) : False**

State S1 is unreachable

Question 151 |

_{1}and S

_{2}given as :

S

_{1}: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.

S

_{2}: There exists an algorithm to determine whether two context free grammars generate the same language.

Which of the following is true ?

S _{1} is correct and S_{2} is not correct. | |

Both S _{1} and S_{2} are correct. | |

Both S _{1} and S_{2} are not correct. | |

S _{1} is not correct and S_{2} is correct. |

**Decidable**

S2 : Equality problem of CFG(check equivalence of 2 CFL'S) -

**Undecidable**

Question 152 |

Have the same number of edges | |

Have the same number of states | |

Recognize the same set of tokens | |

Have the same number of states and edges |

Question 153 |

Any string of odd number of a’s | |

Any string of odd number of b’s | |

Any string of even number of a’s and odd number of b’s | |

Any string of odd number of a’s and odd number of b’s |

{ ab , ba, aaab ,bbba,ababab,abbb, aaabbb ....... }

Question 154 |

0 | |

1 | |

1 or more | |

2 or more |

- FA = 0 stack
- FA + 1 stack = Push Down Automata(PDA)
- FA + 2 stack = Turing Machines
- PDA + 1 stack = Turing Machines

Question 155 |

Only context free grammar | |

Only regular grammar | |

Context free grammar or regular grammar | |

Only context sensitive grammar |

Question 156 |

2n−1 | |

2n | |

N+1 | |

N ^{2} |

A→BC or

A→a or

S→ε

Where S is start symbol and A,B and C are nonterminal symbols, a is a terminal symbol

neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the context-free grammar G.

In CNF at every step only 1 terminal can replace a variable, for example

S−AB

A−a

B−c

For generating string 'ac' 3 productions will be used.

S→AB

S→aB

S→ac.

The number of productions to be used in CNF :

**2n – 1**

**Note:**

Language does not include empty string(S→ε ), then it is CRF (Chomsky reduced form).

Question 157 |

Finite state machine | |

Deterministic finite automata | |

Non-deterministic finite automata | |

Linear bounded automata |

Click this link for more explanation : https://academyera.com/ugc-net-june-paper-2-2018

Question 158 |

^{n} 1

^{n} 2

^{n} | n=1, 2, 3, ......... } is an example of a grammar that is :

Context sensitive | |

Context free | |

Regular | |

None of the above |

Question 159 |

S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.

S2 : The problem of determining whether a Turing machine halts on any input is undecidable.

Which of the following options is correct ?

Both S1 and S2 are correct | |

Both S1 and S2 are not correct | |

Only S1 is correct | |

Only S2 is correct |

Question 160 |

Context free language | |

Context sensitive language | |

Regular language | |

None of the above |

Question 161 |

|Q| | |

2|Q| | |

2|Q| – 1 | |

2^|Q| |

^{n}

Thus Given number of states in NFA = |Q|

After converting from NFA to DFA

Maximum number of states in equivalent DFA = 2

^{|Q|}

Question 162 |

^{n}b

^{m}| n ≤ m + 3, n ≥ 0, m ≥ 0} is

S → aaa A; A → aAb | B, B → Bb | λ | |

S → aaaA|λ, A → aAb | B, B → Bb | λ | |

S → aaaA | aa A | λ, A → aAb | B, B → Bb| λ | |

S → aaaA | aa A | aA | λ, A →aAb | B, B → Bb | λ |

So Such strings are λ, a, aa, aaa

**option(A) : False**

It can't generate the string "a, aa"

**option(A) : False**

It can't generate the string "a, aa"

**option(A) : False**

It can't generate the string "a"

**option(D) : True**

It can generate all strings in the Language L

Question 163 |

**S**If L is a regular language then the language {uv | u ∈ L, v ∈ L

_{1}:^{R}} is also regular.

**S**L = {ww

_{2}:^{R}} is regular language. Which of the following is true ?

S _{1} is not correct and S_{2} is not correct. | |

S _{1} is not correct and S_{2} is correct. | |

S _{1} is correct and S_{2} is not correct. | |

S _{1} is correct and S_{2} is correct. |

^{R}:

**S1 is Correct**

- If L is regular Language then reversal of L(L
^{R}) is also regular Language. Regular Language are closed under Reversal operation . Hence u and v are Regular language - Regular Languages are closed under Concatenation operation
- Therefore UV is Regular Language

**S2 is Incorrect**

- In order to find WW
^{R }"W" need to be remember to match with "W^{R}" - Since Finite Automata don't have any memory so we cant implement using FA but we can implement using NPDA
- NPDA because it have 1 stack able to remember W

Question 164 |

**(I).**Recursive languages are closed under complementation.

**(II).**Recursively enumerable languages are closed under union.

**(III).**Recursively enumerable languages are closed under complementation.

Which of the above statements are true ?

I only | |

I and II | |

I and III | |

II and III |

→Recursively enumerable languages are closed under union, intersection, concatenation ......etc. Except Complementation and Set-difference

Question 165 |

Context-free languages are closed under union. | |

Context-free languages are closed under concatenation. | |

Context-free languages are closed under intersection. | |

Context-free languages are closed under Kleene closure |

Question 166 |

The Pigeon-hole principle | |

The divide and conquer technique | |

Recursion | |

Iteration |

Question 167 |

**S ⟶ XY**

**X ⟶ aX | bX | a**

**Y ⟶ Ya | Yb |a**

Has at least one b | |

Should end in an ‘a’ | |

Has no consecutive a’s or b’s | |

Has at least two a’s |

**option(A) : False**

S ⟶ XY⟶ aY⟶ aa

No b in "aa"

**option(B) : False**

S ⟶ XY⟶ aY⟶ aYb⟶ aab

Ends with b Not end's with a

**option(C) : False**

S ⟶ XY⟶ aY⟶ aYb⟶ aab

"aab" consecutive a's

**option(D) : True**

Language generated by this grammar ={aa,aab,aaa...}

contains at least 2 a's

Question 168 |

**L3 = L1/L2**(right quotient) is given by

A*b | |

A*baa* | |

A*ba* | |

None of the above |

length 2 in L1 = {ba}

length 3 in L1 = {aba,baa}.

length 4 in L1 = {abaa,aaba,baaa}.

**L1={a*baa*}={ba,aba,abaa,abaaa*,aa*baaa*,a*ba*a.....}**

length 1 in L2 = {a}.

length 2 in L2 = {ab}.

length 3 in L2 = {abb}.

length 4 in L2 = {abbb}.

**L2={ab*}={a,ab,abbb,abb*...}**

**L1/L2={x: xy belongs to L1 for some y belongs to L2}**

L1={a*baa*}={ba,aba,abaa,abaaa*,aa*baaa*,a*ba*a.....}

L2={ab*}={a,ab,abb*...}

**L1/L2=a*ba* ={b,ab,aba,abaa,a*baa....}**

option(C) is correct

Question 169 |

5 | |

4 | |

3 | |

2 |

The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is 4

Question 170 |

Of finite tape length, rewinding capability and unidirectional tape movement. | |

Of finite tape length, without rewinding capability and unidirectional tape movement. | |

Of finite tape length, without rewinding capability and bidirectional tape movement. | |

Of finite tape length, rewinding capability and bidirectional tape movement. |

- Finite tape length
- Without rewinding capability
- Unidirectional tape movement.

Question 171 |

The output of the former depends on the present state and the current input | |

The output of the former depends only on the present state | |

The output of the former depends only on the current input | |

None of the above |

**→Moore Machine**Output depends only upon present state.

→In Moore Machine If input changes, output does not change.

**→Mealy Machine**Output depends on present state as well as present input.

→In Mealy Machine If input changes, output also changes.

Question 172 |

**(i)**a

**(ii)**aba

**(iii)**abaabaaba

**(iv)**abaabaabaabaabaabaabaabaaba

Using this as an information, how would you compare the following regular expressions ?

**(i)**(aba)

^{3x }

**(ii)**a.(baa)3

^{x}–1. ba

**(iii)**ab.(aab).

^{3x–1}.a

(ii) and (iii) are same, (i) is different. | |

(ii) and (iii) are not same. | |

(i), (ii) and (iii) are different. | |

(i), (ii) and (iii) are same. |

If you observe clearly all of them above is generating (aba)x

This question is ambiguous, the wordings are not clear.

Question 173 |

Regular | |

Context-sensitive | |

Context free | |

None of the above |

Question 174 |

Context sensitive grammar | |

Non context free grammar | |

Context free grammar | |

None of the above |

**Regular Expression**

(a|b) (a|b|01)

**Context free grammar**

S → aA|bA

A → aA|bA|0A|1A|ε

Question 175 |

Finite state automata | |

2-way linear bounded automata | |

Pushdown automata | |

Both (B) and (C) |

Question 176 |

Type 0 | |

Type 1 | |

Type 2 | |

Type 3 |

Question 177 |

Then L(M), the language accepted by the machine M, is the set of all strings having :

Two or more b’s. | |

Three or more b’s. | |

Two or more a’s. | |

Three or more a’s. |

→So, The language contain 0 occurrence or more occurrence of a's and 2 or more occurrence of b's.

→So we can strike off options B,C,D

option(A) is correct

Question 178 |

Set of all strings containing ‘ab’ | |

Set of all strings containing ‘aab’ | |

Set of all strings ending in ‘abab’ | |

None of the above |

Question 179 |

r=(1+01)* (0+λ)

r=(1+01)* (0+λ)

Set of all string not containing ‘11’ | |

Set of all string not containing ‘00’ | |

Set of all string containing ‘01’ | |

Set of all string ending in ‘0’ |

**option A: Incorrect**

It can generate 11111 which contains 11

**option B: Correct**

No string contains contains "00"

**option C: Incorrect**

It can generate 11 so not all strings contains 01

**option D : Incorrect**

It can end with 01

Question 180 |

Whether two given regular expressions are equivalent | |

A given grammar is ambiguous | |

A given grammar is regular | |

A given grammar is not regular |

Question 181 |

To determine if two finite automata are equivalent | |

Membership problem for context free grammar | |

Finiteness problem for finite automata | |

Ambiguity problem for context free grammar |

Ambiguity problem for context free grammar is undecidable.

**Decidable Problems**

**Equivalence of two regular languages:**Given two regular languages, there is an algorithm and Turing machine to decide whether two regular languages are equal or not.**Finiteness of regular language:**Given a regular language, there is an algorithm and Turing machine to decide whether regular language is finite or not.**Emptiness of context free language:**Given a context free language, there is an algorithm whether CFL is empty or not.**Membership problem for a context-free language**is decidable because of CYK algorithm or any CFL parsing algorithm.

**Undecidable Problems**

**Ambiguity of context-free languages:**Given a context-free language, there is no Turing machine which will always halt in finite amount of time and give answer whether language is ambiguous or not.**Equivalence of two context-free languages:**Given two context-free languages, there is no Turing machine which will always halt in finite amount of time and give answer whether two context free languages are equal or not.**Everything or completeness of CFG:**Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*)is undecidable.**Regularity of CFL, CSL, REC and REC:**Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable.

Question 182 |

Only context free grammar | |

Only context sensitive grammar | |

Only regular grammar | |

Any unambiguous grammar |

- Finite state machine can recognize language generated by regular grammar only.
- Pushdown automata can recognize language generated by Context free grammar or regular grammar.
- Context sensitive grammar generates Context sensitive language
- Context sensitive language can be recognized by a linear bounded automata.

Question 183 |

^{i}b c

^{i}│ i >= 0} over the alphabet {a, b, c} is:

A regular language. | |

Not a deterministic context free language but a context free language. | |

Recursive and is a deterministic context free language. | |

Not recursive. |

**L = {a**has only 1 comparison that can be done using a Deterministic PDA. Hence , its Deterministic CFL.

^{i}b c^{i}│ i >= 0}We can design a deterministic pushdown automata for the given language.

- For each occurrence of ‘a’ , we PUSH X in the stack.
- When ‘b’ appears, no stack operation is performed. But state of the automata is changed.
- For each occurrence of ‘c’ , we POP X from the stack.
- If at the end Z
_{0}is on the stack top then input string is accepted

∴ It is recursive too.

Question 184 |

Every recursive language is recursively enumerable. | |

L = {0 ^{n}1^{n} 0^{n} │n=1, 2 , 3, ....} is recursively enumerable. | |

Recursive languages are closed under intersection. | |

Recursive languages are not closed under intersection. |

**True :**Every recursive language is recursively enumerable.

**True :**L = {0

^{n}1

^{n}0

^{n}│n=1, 2 , 3, ….} is recursively enumerable.

**True :**Recursive languages are closed under intersection.

**False :**Recursive languages are not closed under intersection

Recursive languages are closed under intersection

Question 185 |

Concatenation | |

Complementation | |

Kleene Star | |

Union |

**union**,

**concatenation**and

**Kleene star**

Context-free languages are not closed under

**intersection**or

**complement**.

Question 186 |

L

_{1}= {a

^{m}b

^{n}│ m ≠ n}

L

_{2}= {a

^{m}b

^{n}│ m = 2n+1}

L

_{3}= {a

^{m}b

^{m}│ m ≠ 2n}

Which one of the following statement is correct ?

Only L _{1} and L_{2} are context free languages | |

Only L _{1} and L_{3} are context free languages | |

Only L _{2} and L_{3} are context free languages | |

L _{1}, L_{2} and L_{3} are context free languages |

**L1 = {a**

^{n}b^{m}m!=n }show L11 = a

^{n}b

^{m}n>m is context free and

show L12 = a

^{n}b

^{m}n <m is also context free

Then we know CFL are closed under union then L11 U L12 = {a

^{n}b

^{m}m!=n } is also context free

**Method 2 :**

Given,

L1 = {a

^{n}b

^{m}m!=n }

L = {aab, abb, aaab, abbb, aaaab, aaabb, aabbb, abbbb ......}

In each of the string, the number of a’s are followed by unequal number of b’s. Here, we need to maintain the order of a’s and b’s. That is, all the a’s are are coming first and then all the b’s are coming. Thus, we need a stack along with the state diagram. The count of a’s and b’s is maintained by the stack.

**Approach used in the construction of PDA**

As we want to design a NPDA, thus every time ‘a’ comes before ‘b’. When ‘a’ comes then push it in stack and if again ‘a’ comes then also push it. After that, when ‘b’ comes then pop one ‘a’ from the stack each time. So, at the end if the stack becomes empty and b is coming or string is end and stack is not empty then we can say that the string is accepted by the PDA.

Given,

**L2 = {a**

^{n}b^{m}m=2n+1 }L2 is CFL. We can rewrite it like {a

^{2n+1 }b

^{n}}={a

^{2n}ab

^{n}}={aa

^{2n}b

^{n}}

Given,

**L3 = {a**

^{n}b^{m}m!=2n }L

_{1}, L

_{2}and L

_{3}are context free languages

Question 187 |

**(A)**Strings of even number of a’s.

**(B)**Strings of a’s, whose length is a prime number.

**(C)**Set of all palindromes made up of a’s and b’s.

**(D)**Strings of a’s whose length is a perfect square.

(A) and (B) only | |

(A), (B) and (C) only | |

(B), (C) and (D) only | |

(B) and (D) only |

**Regular**

option(B)Strings of a's , whose length is a prime number.

**This is not Regular but CSL**

option(C)Set of all palindromes made up of a's and b's.

**This is not Regular but CFL**

option(D)strings of a's , whose length is a perfect square.

**This is not Regular but CSL**

Question 188 |

_{1}* ∪ L

_{1}* L

_{2}* ?

{∈} | |

{∈, 1} | |

Φ | |

1* |

**L1* U L1* L2***

L1 is the empty language.

L1* = Φ* which is {ε}. ie , the Kleene closure of the empty language gives the null string always.

We know that for any regular expression R,

R.ε=ε.R=R

L1* L2*

Φ* 1*

ε 1* (L1* = Φ* which is {ε})

=1* (we know that 1.ε=ε.1=1)

**L1* L2* =Φ* 1*=1***

**Now Remaining part :**

L1*

**U**1*

ε

**U**1*

**We know that ε + R=R+ε =R**

ε

**U**1*

=1*

**Note :**

R*+ϵ = ϵ+(ϵ+R)R* = ϵ+ϵR*+RR* = ϵ+R*+RR* = R*+(ϵ+RR*) = R*+R* = R*

option(D) : 1* is correct answer

Question 189 |

**(A)**A class of languages that is closed under union and complementation has to be closed under intersection.

**(B)**A class of languages that is closed under union and intersection has to be closed under complementation.

Which of the following options is correct?

Both (A) and (B) are false. | |

Both (A) and (B) are true. | |

(A) is true, (B) is false. | |

(A) is false, (B) is true. |

**True :**A class of languages that is closed under union and complementation has to be closed under intersection because regular language, context sensitive language(CSL) and recursive language are closed under union and complementation and they are also closing under intersection but recursive enumerable(RE) language is closed under union but not under complementation but still it is closed under intersection.

**False :**A class of languages that is closed under union and intersection has to be closed under complementation.

Question 190 |

Log _{K}|W| ≤ h ≤ log_{K}((|W|-1) / k-1) | |

Log _{K}|W| ≤ h ≤ log_{K}(K|W|) | |

Log _{K}|W| ≤ h ≤ K log_{K}|W| | |

Log _{K}|W| ≤ h ≤ ((|W|-1) / k-1) |

**G = (V, T, S, P)**be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that

**Log**

_{K}|W| ≤ h ≤ ((|W|-1) / k-1)A fairly simple question involving some counting of leaves in a tree. The major purpose is to get students to think about derivation trees. To get the answer, establish a relation between the height of the derivation tree and the maximum number of leaves. For a tree of height h, the maximum number is

**h**. The other extreme is when there is only one node (i.e., there is only one variable in v). In this case, each level except the last has k − 1 leaves, so

^{k}**|w − 1| = h (k − 1)**.

Question 191 |

**L**

_{1}= { a^{n}b^{n}| n ≥ 0, n ≠ 100 }**L**

_{2 }= { w ∈ {a, b, c}*| n_{a}(w) = n_{b}(w) = n_{c}(w) }Which of the following options is correct ?

Both L _{1} and L_{2} are not context free language | |

Both L _{1} and L_{2} are context free language. | |

L _{1} is context free language, L_{2} is not context free language. | |

L _{1} is not context free language, L_{2} is context free language. |

Question 192 |

**A.**L = {w|n

_{a}(w) = n

_{b}(w)} is deterministic context free language, but not linear.

**B.**L = {a

^{n}b

^{n}} ∪ {a

^{n}b

^{2n}} is linear, but not deterministic context free language.

Which of the following options is correct ?

Both (A) and (B) are false. | |

Both (A) and (B) are true. | |

(A) is true, (B) is false. | |

(A) is false, (B) is true. |

L = {w|n

_{a}(w) = n

_{b}(w)} is deterministic context free language, but not linear.

L = {a

^{n}b

^{n}} ∪ {a

^{n}b

^{2n}} is linear, but not deterministic context free language

Question 193 |

Single-tape-turing machine and multi-dimensional turing machine. | |

Multi-tape turing machine and multi-dimensional turing machine. | |

Deterministic pushdown automata and non-deterministic pushdown automata. | |

Deterministic finite automata and Non-deterministic finite automata |

- Single Tape Turing machine and multi-dimensional Turing machine have same expressive power.
- Multi Tape Turing machine and multi-dimensional Turing machine have same expressive power.
- Deterministic push down automata and Non-deterministic push-down automata have different expressive power(NPDA is more expressive then DPDA)
- NDPDA can handle languages or grammars with ambiguity, but DPDA cannot handle languages with ambiguity and any context-free grammar
- NPDA cannot be converted into DPDA.

- Deterministic finite automata and Non-deterministic finite automata have same expressive power.
- DFA and NFA are of same power because we can convert every NFA into DFA and and vice-versa

Question 194 |

Every context-sensitive language is recursive. | |

The set of all languages that are not recursively enumerable is countable. | |

The family of recursively enumerable languages is closed under union. | |

The families of recursively enumerable and recursive languages are closed under reversal. |

**option(A) :**True

Every context-sensitive language is recursive.

According to Chomsky Hierarchy Context Sensitive Languages are the subset of recursive languages

**option(B)**: False

**Theorem:**Some languages are not recursively enumerable.

**Proof:**The set of strings is an infinite countable set.

The set of languages is not countable because it is the powerset of the set of strings.

Recursively enumerable languages are countable because TMs are countable.

Therefore, recursively enumerable languages

**⊂**all languages.

**option(C) :**True

The family of recursively enumerable languages is closed under union

**option(D) :**True

The families of recursively enumerable and recursive languages are closed under reversal

Question 195 |

^{n}b

^{m }| n ≥ 4, m ≤ 3 } is:

(λ + a + aa + aaa) b* + a* bbbb* + (a + b)* ba(a + b)* | |

(λ + a + aa + aaa) b* + a* bbbbb* + (a + b)* ab(a + b)* | |

(λ + a + aa + aaa) + a* bbbbb* + (a + b)* ab(a + b)* | |

(λ + a + aa + aaa)b* + a* bbbbb* + (a + b)* ba(a + b)* |

**L = {a**is L =

^{n}b^{m }| n ≥ 4, m ≤ 3 }**{a**

^{n}b^{m}|n < 4} U {a^{n}b^{m }| m > 3}**option(A)**: Using the term a*bbbb* it can accept a

^{4}b

^{3}thus, it is not complemented

**option(B)**: Using (a+b)* ab (a+b)* it can accept a

^{4}b

^{3}thus, it is not complemented

**option(C)**: Using (a+b)* ab (a+b)* it can accept a

^{4}b

^{3}thus, it is not complemented

**option(D)**: (a+b)* ba (a+b)* cannot produce strings in a

^{n}b

^{m}format and other 2 terms cannot produce any string a

^{n}b

^{m}such that n>=4 and m<=3 and it produce produce any string a

^{n}b

^{m}such that n < 4 and m > 3

option(D) is correct answer

Question 196 |

**L**

_{1}= {0^{i}1^{j}| gcd (i, j) = 1}**L**

_{2}is any subset of 0*.Which of the following is correct ?

L _{1} is regular and L_{2}* is not regular | |

L _{1} is not regular and L_{2}* is regular | |

Both L _{1} and L_{2}* are regular languages | |

Both L _{1} and L_{2}* are not regular languages |

Question 197 |

_{M}defined by M. As all states are reachable from the start state, R

_{M}has _____ equivalence classes.

2 | |

4 | |

5 | |

6 |

Question 198 |

**L = {0**be a context free language. Which of the following is correct ?

^{n}1^{n}|n ≥ 0}L’ is context free and L ^{k} is not context free for any k ≥ 1. | |

L’ is not context free and L ^{k} is not context free for any k ≥ 1. | |

Both L’ and L ^{k} is for any k ≥ 1 are context free. | |

Both L’ and L ^{k} is for any k ≥ 1 are not context free. |

**L= {a**is L =

^{n }b^{n }: n ≥ 0}**{a, b}**

^{*}- {a^{n }b^{n}: n ≥ 0}• So we look at how a string could fail to be in

**a**

^{n}b^{n}• There are 2 ways: either the a’s and b’s are out of order or there are not equal numbers of them. So our language L is the union of two other languages:

•

**L1 = (a ∪ b)* - a*b***(strings where the a’s and b’s are out of order)

•

**L2 = a**(strings where the a’s and b’s are in order but there aren’t matching numbers of them)

^{n }b^{m}n ≠ mL1 is context free. We gave a context-free grammar for it in class.

L2 is the complement of the regular language

**a*b***, so it is also regular and thus context free.

Since the union of two context-free languages is context free, L is context free

Question 199 |

**M = ({q**

_{0}, q_{1}, q_{2}, q_{3}}, {a, b}, {a, b, B}, δ, B, {q_{3}})Where δ is a transition function defined as

**δ(q**

_{0}, a) = (q_{1}, a, R)**δ(q**

_{1}, b) = (q_{2}, b, R)**δ(q**

_{2}, a) = (q_{2}, a, R)**δ(q**

_{3}, b) = (q_{3}, b, R)The language L(M) accepted by the Turing Machine is given as:

Aa*b | |

abab | |

aba*b | |

aba* |

**Given transition,**

δ(q0, a) = (q1, a, R)

δ(q1, b) = (q2, b, R)

δ(q2, a) = (q2, a, R)

δ(q3, b) = (q3, b, R)

From Given transition, We can build DFA

language L(M) accepted by the Turing machine is aba*b.

Question 200 |

**L = {a**is given by

^{n}b^{m}| n + m is even}S → S _{1} | S2S _{1} → a S_{1}| A_{1}A _{1} → b A_{1}| λ S _{2 }→ aaS_{2}| A_{2 }A _{2} → b A_{2}| λ | |

S → S _{1 }| S_{2}S _{1 }→ a S_{1}| aA_{1}S _{2} → aaS_{2} | A_{2} A _{1} → b A_{1}| λ A _{2} → b A_{2}| λ | |

S → S _{1} | S_{2}S _{1 }→ aaa S_{1}| aA_{1} S _{2} → aaS_{2}| A_{2} A _{1} → b A_{1}| λ A _{2} → b A_{2}| λ | |

S → S _{1} | S_{2}S _{1} → aa S_{1 }| A_{1}S _{2} → aaS_{2} | aA_{2}A _{1} → bbA_{1} | λA _{2} → bbA_{2} | b |

For n+m to be even There are two cases:

- n and m are even: (aa)*(bb*)
- n and m are odd: a(aa)*b(bb*)

Thus, a regular expression for the set {a

^{n}b

^{m}: (n + m) is even} is (aa)*(bb*) +a(aa)*b(bb*).

option (A), option (B) and option (C) are not correct because it can generate sting like {

**aab**,

**aaaab**} which are odd

option(D) is correct answer it can generate strings like {

**$**,

**ab**,

**aa**,

**bb**,

**abbb**,

**aaab**,

**aabb**,

**aaab**.......} which is even

- S→S1|S2
- S1→aaS1|A1
**→**Hear A1 derives even number of b's and S1 derives even number of a's - S2→aaS2|aA2
**→**Hear A2 derives odd number of b's and aA2 will have even number of a's and b's - A1→bbA1|λ→ Hear we get even number of b's
- A2→bbA2|b →Hear we get odd number of b's

Question 201 |

{λ, a, b, ab, ba} ∪ {w∈{a, b}* | |w| > 3} | |

{a, b, ab, ba} ∪ {w∈{a, b}* | |w| > 3} | |

{w ∈ { a, b}* | |w| > 3} ∪ {a, b, ab, ba} | |

{λ, a, b, ab, ba} ∪ {w ∈ {a, b}* | |w| ≥ 3} |

Complement will be universal set of strings – {aa, bb}.

L

^{c}= Σ* - L

L

^{c}= Σ* - {aa, bb}

**L**and strings {

^{c}= { λ, a, b, ab, ba }**w**∈

**{a, b}***|

**|w| ≥ 3**},

i.e. strings of length greater than or equal to 3.

Question 202 |

**(a) (r + s)* = (s + r)***

**(b) (r*)* = r***

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

Which of the above identities are true?

(a) and (b) only | |

(b) and (c) only | |

(c) and (a) only | |

(a), (b) and (c) |

(a) (r + s)* = (s + r)*

(b) (r*)* = r*

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

Any string constructed by LHS can also constructed by RHS and vice-versa

We can generate any strings by using (r + s)* which containing r or s or both or epsilon. and we can also construct DFA for (r + s)* which is same as (s + r)*.

Question 203 |

**L**= { uww

_{1}^{R}ν | u, v, w ∈ {a, b}

^{+ }}

**L**= { uww

_{2}^{R}ν | u, ν, w ∈ {a, b}

^{+}, |u| > |ν| }

Which of the following is correct ?

L _{1} is regular language and L_{2} is not regular language. | |

L _{1} is not regular language and L_{2} is regular language. | |

Both L _{1} and L_{2} are regular languages. | |

Both L _{1} and L_{2} are not regular languages. |

**option(A) is the correct answer L1 is regular and L2 is non-regular.**

**L1 = {uww**L1 is regular. This may seem counterintuitive. But any string of length at least four with two consecutive symbols, not including the first and the last ones, is in L. We simply make everything up to the first of the two consecutive symbols u. The first of the two consecutive symbols is w. The second is w

^{R}v : u, v, w ∈ {a, b}^{+}}.^{R}. And the rest of the string is v. And only strings with at least one pair of consecutive symbols (not including the first and last) are in L because w must end with some symbol s. w

^{R}must start with that same symbol s. Thus the string will contain two consecutive occurrences of s. L is regular because it can be described the

**Regular expression for L1 : r1=**(a + b)

^{+}(aa + bb) (a + b)

^{+}

**L2 = {uww**; L2 is not regular.

^{R}ν | u, ν, w ∈ {a, b}^{+}, |u| > |ν|}In Language L2 we need stack to compare length of u and v which can't be done by DFA.

So,L2 is not regular language

Question 204 |

**M = ({q0 , q1 }, {0, 1}, {0, 1, B}, δ, B, {q1 })**

Where δ is a transition function defined as

**δ(q0 , 0) = (q0 , 0, R)**

**δ(q0 , B) = (q1 , B, R)**

The language L(M) accepted by Turing machine is given as :

0* 1* | |

00* | |

10* | |

1*0* |

**Definition**

what must happen when w ∈ Γ L (M). It says nothing about the outcome for any other input. When w is not in L (M), one of two things can happen: The machine can halt in a nonfinal state or it can enter an infinite loop and never halt. Any string for which M does not halt is by definition not in L(M).

Starting at the left end of the input, we read each symbol and check that it is a 0. If it is, we continue by moving right. If we reach a blank without encountering anything but 0, we terminate and accept the string. If the input contains a 1 anywhere, the string is not in L(00*), and we halt in a nonfinal state. To keep track of the computation, two internal states Q= {q0,q1}and one final state F= {q1} are sufficient. As transition function we can take As long as a 0 appears under the read-write head, the head will move to the right. If at any time a 1 is read, the machine will halt in the nonfinal state q0, since δ(q0,1) is undefined. Note that the Turing machine also halts in a final state if started in state q0 on a blank. We could interpret this as acceptance of λ, but for technical reasons the empty string is not included in above Definition.

**δ(q0 , 0) = (q0 , 0, R)**

**δ(q0 , B) = (q1 , B, R)**

Question 205 |

H<((|W| - 1)/k-1) | |

Log _{k}|W| < h | |

Log _{k}|W| < h < ((|W| - 1)/k-1) | |

Log _{k}|W| <= h <= ((|W| - 1)/k-1) |

**G = (V, T, S, P)**be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that

**Log**

_{K}|W| ≤ h ≤ ((|W|-1) / k-1)A fairly simple question involving some counting of leaves in a tree. The major purpose is to get students to think about derivation trees. To get the answer, establish a relation between the height of the derivation tree and the maximum number of leaves. For a tree of height h, the maximum number is

**h**. The other extreme is when there is only one node (i.e., there is only one variable in v). In this case, each level except the last has k − 1 leaves, so

^{k}**|w − 1| = h (k − 1)**.

Question 206 |

Closed, not closed | |

Not closed, not closed | |

Closed, closed | |

Not closed, closed |

**closed**under union and

**closed**under reversal.

Question 207 |

List - IList - II(a){a^{n}b^{n}| n > 0} is a deterministic(i)but not recursive language context free language(b)The complement of {a^{n}b^{n}a^{n}| n > 0}(ii)but not context free language is a context free language(c){a^{n }b^{n}a^{n}} is context sensitive language(iii)but can not be accepted by a deterministic pushdown automation(d)L is a recursive language(iv)but not regular

(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv) | |

(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii) | |

(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i) | |

(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii) |

- a
^{n}b^{n}| n > 0 } is a deterministic context free language but not regular language

There exists at least one language that is CFL but not regular.

**a**From this we can understand that regular languages are a proper subset of the context-free languages.^{n}b^{n}| n > 0 } is a context free language but not regular language

- The complement of {a
^{n}b^{n}a^{n}| n > 0 } is context free language but not accepted by deterministic pushdown automata.

{**a**} is not context free language but it's complement is Context free language and we can implement by using NPDA.^{n}b^{n}a^{n}| n > 0 - {a
^{n}b^{n}a^{n}} is a context sensitive language but not context free language - L is a recursive language but not a context free language

**Note**: option(D) not clear. Excluded from evaluation

Question 208 |

**S → aS|Sa|a**

The word

**a**can be generated by __________ different trees.

^{3}Two | |

Three | |

Four | |

Five |

^{3}can be generated by four different trees.

Question 209 |

**S → XYX**

**X → aX|bX|λ**

**Y → bbb**

generates the language which is defined by regular expression:

(a + b)*bbb | |

Abbb(a + b)* | |

(a + b)*(bbb)(a + b)* | |

(a + b)(bbb)(a + b)* |

S → XYX

X → aX|bX|λ

Y → bbb

The equivalent RE for above grammar is:

**(a + b)*(bbb)(a + b)***

which is equivalent to Set of all string containing

**bbb**as substring.

**Trick :**

X → aX|bX|λ can generate (a + b)*

Y → bbb is generating bbb

hear "bbb" will be in the middle

So,

S → XYX

(a + b)* bbb (a + b)*

Question 210 |

64 | |

56 | |

1024 | |

5832 |

Therefore, x=3 and y=2

**Number of different automata**= 2

^{x}* x

^{xy }

=( 2

^{3}* 3

^{(3*2) })

=2

^{3}* 3

^{6 }=8*729

=5832

Question 211 |

**L**

_{1}= {a^{n }b a^{n }| n > 0}**L**

_{2}= {a^{n}b a^{n }b^{n + 1 }| n > 0}Which of the following is correct ?

L _{1 }is context free language and L_{2 }is not context free language | |

L _{1 }is not context free language and L_{2 }is context free language | |

Both L _{1} and L_{2 }are context free languages | |

Both L _{1} and L_{2 }are not context free languages |

**L1 = {a**

^{n}b a^{n}| n > 0} which is CFLpush a′s into stack , do nothing with b , then pop all a′s from stack on reading a′s at the end there will be $ in the bottom of stack and we will accept that string. we can implement this by using DPDA

**L2 = {a**but

^{n}b a^{n}b^{n}+ 1 | n > 0} which is not CFL**CSL**

For L2, in addition to above comparison, we also need to ensure number of b's following the a's is just one more. This cannot be done with single stack. So, this makes L2 is not Context Free Language but we can implement using CSL

Option(A), L1 is context free and L2 is not context free language.

Question 212 |

Strong Transmitter | |

Polling | |

Segmentation | |

Modulation |

**Signal balancing**is needed to limit the signal over certain limit; not too weak to attenuate across the medium before reaching far stations and not too strong to cause distortion, in both cases cannot be recovered.

This can be done within certain limit and also this limit the bus length. To increase the length of the LAN, the bus is split into

**segments**joined by repeaters (transparent device); to overcome the impairments effects; in a non closed way.

Question 213 |

Turing machine is a simple mathematical model of general purpose computer | |

Turing machine is more powerful than finite automata | |

Turing Machine can be simulated by a general purpose computer | |

All of these |

**True :**Turing machine is a simple mathematical model of general purpose computer

A Turing machine is a mathematical model of computation that defines an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed

**True :**Turing machine is more powerful than finite automata

Let us take an example to show Turing machine is more powerful than finite automata : A finite state machine can recognize a sequence that has three A's followed by three Bs e.g. AAABBB and so can a Turing machine. But only a Turning machine can recognize a sequence that has an arbitrary number of As followed by the same number of B's. That is a Turing machine is more powerful than a finite state machine because it can count.

**True :**Turing Machine can be simulated by a general purpose computer

Refer : https://arxiv.org/abs/1203.4667