NFA | Non Deterministic Finite Automata Questions-Answers – Theory of Computation

#### Show Answer With Best Explanation

Explanation:
Regular language does not have any memory to compare.
A. L={ (01)n0k | n > k, k>=0 }
Here, occurance of n is greater than occurance of k, for that we need to compare value of n with k, and regular language does not have power to compare. so,it is not regular language. It is Context Free Language.

B. L={ cnbkan+k | n >= 0, k>=0 }
Here, occurance of c is less than or equal to ocuurance of a and Finite Automata cannot do this comparison. So, it is not regular language . It is Context Free Language.

C. L={ 0n1k | n≠k }
Here, occurance of n is not equal to occurance of k, and this type of comparison cannot be done by Finite Automata.So, it is also not regular language . It is Context Free Language.

So, Option(III) is correct.

#### Show Answer With Best Explanation

Explanation:
Given,
pushdown automata M=({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2})
where,
{q0, q1, q2} = Finite state of states
{a, b} = Input alphabet
{a, b, z} = Stack alphabet
δ = Transition Function
q0 = Initial state
z = Bottom of the stack
{q2} = Final state
Let’s Draw pushdown automata for a given Transition function: First, keep pushing any number of a’s and b’s in the stack , and then pop one a from stack on seeing input alphabet a and pop one b from stack on seeing input alpbabet b. Keep popping untill we reach end of string λ. when we reach end of string λ and Top of Stack is z, then go to final state.
Let’s take one string and analyze them
suppose string Language generated by above push down automata (L)= {wwR | w Є {a, b}+}
So, Option(IV) is correct.

#### Show Answer With Best Explanation

Explanation:
Statement A: L3 =L1 ∩ L2
L1 = { 0n1n0m | n>=1, m>=1 }
= {010, 0100, 00110, 001100……………………}
L2 = { 0n1m0m | n>=1, m>=1 }
= {010, 0010, 01100, 001100…………………. }
L3 =L1 ∩ L2
= {010, 001100, 000111000…………………….}
= {0n1n0n | n>=1}
Statement A is correct.
Statement B: L1 and L2 are context free languages but L3 is not a context free language
L1 = { 0n1n0m | n>=1, m>=1 }
let’s draw push down automata for above language: =1, m>=1 }”>
Language L2 is Context Free Language.

L3 = { 0n1n0n | n>=1}
Here, n times 0 followed by n times 1 followed by n times 0, this kind of comparison cannot be done by Push Down Automata. So, it is not Context Free Language. It is Context Sensitive Language.
Statement B is correct.

Statement C: L1 and L2 are not context free languages but L3 is a context free language
As statement B is correct, Statement C is obviously incorrect.

Statement D: L1 is a subset of L3
L1 = { 0n1n0m | n>=1, m>=1 }
= {010, 0100, 00110, 001100……………………}
L3 ={ 0n1n0n | n>=1}
= {010, 001100, 000111000…………………….}
As see, L1 is superset L3
Statement D is incorrect.
So, Option(IV) is correct.

#### Show Answer With Best Explanation

Explanation:
S-> XY
->0XY | 1XY | 0Y
->0XY0 | 0XY1 | 0X0 | 1XY0 | 1X0 | 0Y0 | 0Y1 | 00
->0XY0 | 0XY1 | 000 | 1XY0 | 100 | 000 | 001 | 00

Option(i): has at least one 1
This is incorrect, because one of the string of above language is 00 which don’t contain 1.

Option(ii): has no consecutive 0’s or 1’s
This is incorrect, because one of the string of above language is 100 which has consecutive 0’s.

Option(iii): should end with 0
This is incorrect, because one of the string of above language is 001 which ends with 1.

Option(iv): has at least two 0’s
This is correct. Because X and Y always end with 0, so string has atleast two 0’s.

#### Show Answer With Best Explanation

Explanation:
DFA Minimization
Two state p,q are said to be equivalent if
δ(p,w) ϵ F => δ(q,w) ϵ F
and

#### Show Answer With Best Explanation

Answer: (Marks to all from UGC NET )

#### Show Answer With Best Explanation 