1,983 views

1 Answer

0 votes
0 votes
Here these theorems are based on pigeon hole principle.

1. Here it says that strings accepted by automata is finite, than atmost n states can be there. This means at most one character can be fit in a single state.

2. Now consider what if this is accepting a string of more than n characters than according to Pigeon hole principle, there should be at least one state on which input is looping. So this may accept infinite length of strings when looping state is accepting as well.

In order to check this, we have two options one is to provide all strings till infinite length and check. Obviously not feasible.

Another approach is to provide all strings of length between n and 2n. So if anyone string is accepted we will know that looping state is accepting as well so this language will accept all those strings on which it will loop on that particular state. So it will be a set of infinite strings.

Related questions

1 votes
1 votes
0 answers
1
1 votes
1 votes
0 answers
2
rahul sharma 5 asked Jul 31, 2017
560 views
If FA has length n and accepting the string of more than n,then can i say that it must accept the string of length less than n also?
1 votes
1 votes
2 answers
4
iarnav asked Sep 1, 2018
25,800 views
How to construct a finite automata equivalent to the regular expression: ( 0 + 1 )* ( 00 + 11 ) ( 0 + 1 )*