Register

Test by Bikram | Theory of Computation | Test 2 | Question: 6

• retagged by
274 views

1 Answer

Best answer
4 votes
4 votes

The number of x's is at least  L.

For simplicity let L = 4.

The required minimal Finite Automata is

For L = 4, we have 5 States. Similarly For no. of x's is at least  L, We have (L + 1) States.

Note: Here both minimal DFA and minimal NFA have same states. 

An interesting question would be: The no. of states in Minimal finite automata such that no. of x's is exactly L.

Here minimal NFA will have (L + 1) states.

Minimal DFA will have (L + 2) states.

Therefore, Minimal Finite automata will have (L + 1) states.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
2
Bikram asked Aug 12, 2017
478 views
Test by Bikram | Theory of Computation | Test 2 | Question: 9
Consider the following transition table of DFA where $q3$ ... The number of states required to represent the same language with minimum number of states automata is _________.
Consider the following transition table of DFA where $q3$ is the final state:$\begin{array}{|c|c|c|} \hline {} & x & y \\ \hline \rightarrow q0 & q1 & q0 \\ \hline q1 & q...
User Avatar
1 votes
1 votes
1 answer
4
Bikram asked Aug 12, 2017
622 views
Test by Bikram | Theory of Computation | Test 2 | Question: 3
Consider the following input sequence $010101\dots$ ($01$ repeated one or more times). The minimum number of states required in a DFA to accept the strings following the above pattern is _________.
Consider the following input sequence $010101\dots$ ($01$ repeated one or more times).The minimum number of states required in a DFA to accept the strings following the a...
User Avatar
Link Copied!