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

Q1➡ | NET June 2021
Which of the following languages are not regular?
A. L={ (01)n0k | n > k, k>=0 }
B. L={ cnbkan+k | n >= 0, k>=0 }
C. L={ 0n1k | n≠k }
Choose the correct answer from the options given below:
i ➥ A and C only
ii ➥ A and B only
iii ➥ A, B and C
iv ➥ B and C only

Show Answer With Best Explanation

Answer: III
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.

More Discussion Explanation On YouTubeLearn Topic WiseHelp-Line
Q2➡ | NET June 2021
What language is accepted by the pushdown automaton
M=({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2})
with
δ(q0, a, a) ={ (q0, aa) }; δ(q0, b, a) ={(q0, ba)}
δ(q0, a, b) ={ (q0, ab) }; δ(q0, b, b) ={ (q0, bb) }
δ(q0, a, z) ={ (q0, az) }; δ(q0, b, z) ={ (q0, bz) }
δ(q0, λ, b) ={ (q1, b) }; δ(q0, λ, a) ={ (q1, a) }
δ(q1, a, a) ={ (q1, λ) }; δ(q1, b, b) ={ (q1, λ) }
δ(q1, λ, z) ={ (q2, z) }?
i ➥ L = { w | na(w) <= nb(w), w Є {a, b}+}}
ii ➥ L = { w | na(w) = nb(w), w Є {a, b}+}}
iii ➥ L = { w | nb(w) <= na(w), w Є {a, b}+}}
iv ➥ L= {wwR | w Є {a, b}+}

Show Answer With Best Explanation

Answer: IV
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:
What language is accepted by the pushdown automaton M=({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) with δ(q0, a, a) ={ (q0, aa) };
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
What language is accepted by the pushdown automaton M=({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) with
Language generated by above push down automata (L)= {wwR | w Є {a, b}+}
So, Option(IV) is correct.

More Discussion Explanation On YouTubeLearn Topic WiseHelp-Line
Q3➡ | NET June 2021
L1 = { 0n1n0m | n>=1, m>=1 }
L2 = { 0n1m0m | n>=1, m>=1 }
L3 = { 0n1n0n | n>=1}
Which of the following are correct statements?
A. L3 =L1 ∩ L2
B. L1 and L2 are context free languages but L3 is not a context free language
C. L1 and L2 are not context free languages but L3 is a context free language
D. L1 is a subset of L3
Choose the correct answer from the options given below:
i ➥ A and C only
ii ➥ A and D only
iii ➥ A only
iv ➥ A and B only

Show Answer With Best Explanation

Answer: IV
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:
L1 = { 0n1n0m | n>=1, m>=1 }”><br>Language L<sub>1</sub> is Context Free Language.<br><br><strong><strong>L<sub>2</sub> </strong></strong>= { 0<sup>n</sup>1<sup>m</sup>0<sup>m</sup> | n>=1, m>=1 }<br>let’s draw push down automata for above language:<br><img decoding==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.

More Discussion Explanation On YouTubeLearn Topic WiseHelp-Line
Q4➡ | NET June 2021
Any string of terminals that can generated by the following context free grammar (where S is start non-terminal symbol)

S→XY
X→0X|1X|0
Y→Y0|Y1|0
i ➥ has at least one 1
ii ➥ has no consecutive 0’s or 1’s
iii ➥ should end with 0
iv ➥ has at least two 0’s

Show Answer With Best Explanation

Answer: IV
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.

More Discussion Explanation On YouTubeLearn Topic WiseHelp-Line
Q5➡ | NET June 2021
Match List I with List II

Choose the correct answer from the options below:
i ➥ A – III, B -I , C – IV, D – II
ii ➥ A – III, B -II , C – I, D – IV
iii ➥ A – III, B -IV, C – I, D – II
iv ➥ A – IV, B -III , C – I, D – II

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLearn Topic WiseHelp-Line
Q6➡ | NET June 2021
What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?
i ➥ 3
ii ➥ 4
iii ➥ 5
iv ➥ 6

Show Answer With Best Explanation

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

More Discussion Explanation On YouTubeLearn Topic WiseHelp-Line
Q7➡ | NET June 2021
Given below are two statements
Statement I:
The family of context free languages is closed under homomorphism
Statement II:
The family of context free languages is closed under reversal.
In light of the above statements, choose the correct answer from the options given below
i ➥ Both Statement I and Statement II are false
ii ➥ Both Statement I and Statement II are true
iii ➥ Statement I is false but Statement II is true
iv ➥ Statement I is true but Statement II is false

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLearn Topic WiseHelp-Line
Q8➡ | NET June 2021
Find the regular expression for the language accepted by the automata given below.
i ➥ (a+b)ab(ab+bb+ aa*(a+b)ab)*
ii ➥ (aa*(a+b)ab)*
iii ➥ a*(a+b)ab(ab+bb+ aa*(a+b)ab)*
iv ➥ a*ab(ab+bb+ aa*(a+b)ab)*

Show Answer With Best Explanation

Answer: (Marks to all from UGC NET )
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLearn Topic WiseHelp-Line
Q➡ |NFA
Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
i ➥ Statement 1 can be true and Statement 2 is true
ii ➥ Statement 1 is false and Statement 2 is also false
iii ➥ Statement 1 is true and Statement 2 is true
iv ➥ Statement 1 is true and Statement 2 is false

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
Given Language: L= {ab U aba}*
If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,
|X-Y|=?
i ➥ 4
ii ➥ 3
iii ➥ 2
iv ➥ 1

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
An automaton that presents output based on previous state or current input:
i ➥ Transducer
ii ➥ Acceptor
iii ➥ Classifier
iv ➥ None of the mentioned.

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?
i ➥ 128
ii ➥ 127
iii ➥ 64
iv ➥ 32

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon

Q➡ |NFA
NFA, in its name has ’non-deterministic’ because of :
i ➥ The choice of path is non-deterministic
ii ➥ The state to be transited next is non-deterministic
iii ➥ The result is undetermined
iv ➥ All of the Above

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA
i ➥ Statement 2 is false and Statement 1 is false
ii ➥ Statement 1 is false because Statement 2 is false
iii ➥ Statement 2 is correct because Statement 2 is correct
iv ➥ Statement 1 is correct because Statement 2 is correct

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
Given Language L= {xϵ {a, b}*|x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent NFA?
i ➥ 4
ii ➥ 3
iii ➥ 2
iv ➥ Cannot be able to determined.

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
The construction time for DFA from an equivalent NFA (m number of node)is:
i ➥ O(2m)
ii ➥ O(logm)
iii ➥ O(m2)
iv ➥ O(m)

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
i ➥ log m
ii ➥ 1/m
iii ➥ 2m
iv ➥ 1/m2

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon

Q➡ |NFA
Which of the following option is correct?
i ➥ NFA is slower to process and its representation uses less memory than DFA
ii ➥ DFA is slower to process and its representation uses less memory than NFA
iii ➥ NFA is slower to process and its representation uses more memory than DFA
iv ➥ DFA is faster to process and its representation uses less memory than NFA

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
Subset Construction method refers to:
i ➥ Eliminating Null references
ii ➥ ε-NFA to NFA
iii ➥ Conversion of NFA to DFA
iv ➥ DFA minimization

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
Given Language:
Ln= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L3 using NFA?
i ➥ 5
ii ➥ 14
iii ➥ 15
iv ➥ 16

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
Which of the following does the given NFA represent?
i ➥ {11, 110} * {0}
ii ➥ {00, 110} * {1}
iii ➥ {11, 101} * {01}
iv ➥ {110, 01} * {11}

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
The number of transitions required to convert the following into equivalents DFA:
i ➥ 3
ii ➥ 2
iii ➥ 1
iv ➥ 0

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon

Q➡ |NFA
If L is a regular language, Lc and Lr both will be:
i ➥ Cannot be said
ii ➥ One of them will be accepted
iii ➥ Accepted by NFA
iv ➥ Rejected by NFA

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
In NFA, this very state is like dead-end non final state:
i ➥ REJECT
ii ➥ START
iii ➥ ACCEPT
iv ➥ DISTINCT

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
The production of form non-terminal -> ε is called:
i ➥ Epsilon Production
ii ➥ Sigma Production
iii ➥ Null Production
iv ➥ All of the Above

Show Answer With Best Explanation

Answer: iii
Explanation: Upload Soon

Q➡ |NFA
Which of the following is a regular language?
i ➥ String with even number of Zero’s
ii ➥ Palindrome string
iii ➥ String whose length is a sequence of prime numbers
iv ➥ Which of the following is a regular language?

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
Which of the following recognizes the same formal language as of DFA and NFA?
i ➥ Robin-Scott Construction
ii ➥ Power set Construction
iii ➥ Subset Construction
iv ➥ All of the Above

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
Regarding the power of recognition of languages, which of the following statements is false?
i ➥ Non-deterministic Turing machines are equivalent to deterministic Push-down automata.
ii ➥ Non-deterministic Push-down automata are equivalent to deterministic Push- down automata.
iii ➥ The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
iv ➥ Both A and B

Show Answer With Best Explanation

Answer: iv
Explanation: Upload Soon

Q➡ |NFA
Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?
i ➥ Df = Nf and Dp ⊂ Np
ii ➥ Df = Nf and Dp = Np
iii ➥ Df ⊂ Nf and Dp = Np
iv ➥ Df ⊂ Nf and Dp ⊂ Np

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
Which one of the following is FALSE?
i ➥ Complement of every context-free language is recursive.
ii ➥ Every non-deterministic PDA can be converted to an equivalent deterministic PDA.
iii ➥ There is unique minimal DFA for every regular language.
iv ➥ Every NFA can be converted to an equivalent PDA.

Show Answer With Best Explanation

Answer: ii
Explanation: Upload Soon

Q➡ |NFA
Which of the following pairs have DIFFERENT expressive power?
i ➥ Deterministic push down automata (DPDA) and Non-deterministic push down automata (NFDA)
ii ➥ Single-tape Turning machine and multi-tape Turning machine
iii ➥ Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
iv ➥ Deterministic single-tape Turning machine and Non-deterministic single tape Turning machine

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

Q➡ |NFA
i ➥ {q0,q1,q2}
ii ➥ {q0,q1,q3}
iii ➥ {q0,q2,q3}
iv ➥ ∅

Show Answer With Best Explanation

Answer: i
Explanation: Upload Soon

You should also practice on below topics
Regular Language Mode
Deterministic Finite Automaton (DFA),
Non-Deterministic Finite Automaton (NDFA),
Equivalence of DFA and NDFA,
Regular Languages,
Regular Grammars,
Regular Expressions,

Leave a Reply

Your email address will not be published.

error: Content is protected !!
Open chat
1
Hi,how Can We Help You ?