Prove That There Is No Finite-State Automaton That Accepts the Language

Question

Examlex · Accepted Answer

The Answer is $Suppose not. That is suppose there is a finite-state automaton A that accepts the language L consisting of all strings of x 's and y 's of the form x^{n} y^{n} where n is a positive integer. [A contradiction will be derived.] Since A has only a finite number of states, these states can be denoted s_{1}, s_{2}, s_{3}, \ldots, s_{k} , where k is a positive integer.Consider all input strings that consist entirely of x 's: x, x^{2}, x^{3}, \ldots . Now there are infinitely many such strings and only finitely many states. Thus, by the pigeonhole principle, there must be a state s_{m} and two input strings x^{p} and x^{q} with p eq q such that when either x^{p} or x^{q} are input to A, A goes to state s_{m} . Now, by supposition, A accepts the string x^{p} y^{p} . This means that after p x^{\prime} 's have been input, at which point A is in state s_{m} , inputting p additional b's sends A into an accepting state, say s_{a} . But that implies that inputting x^{q} y^{p} also sends A to s_{a} , which means that x^{q} y^{p} is also accepted by A . The reason is that after q x 's have been input, A is also in state s_{m} , and from that point, we know that inputting p additional b's sends A to state s_{a} , which is an accepting state. Hence x ^ { q } y ^ { p } is in L where p eq q But, by supposition, all the strings in L have the form x ^ { n } y ^ { n } , which have the same number of that there is no finite-state automaton that accepts the language L consisting of all strings of x ^ { \prime } 's and y 's of the form x ^ { n } y ^ { n } where n is a positive integer.$ Suppose not. That is suppose there is a finite-state automaton

A

that accepts the language

L

consisting of all strings of

x

's and

y

's of the form

x^{n} y^{n}

where

n

is a positive integer. [A contradiction will be derived.] Since

A

has only a finite number of states, these states can be denoted

s_{1}, s_{2}, s_{3}, \ldots, s_{k}

, where

k

is a positive integer.Consider all input strings that consist entirely of

x

's:

x, x^{2}, x^{3}, \ldots

. Now there are infinitely many such strings and only finitely many states. Thus, by the pigeonhole principle, there must be a state

s_{m}

and two input strings

x^{p}

and

x^{q}

with

p eq q

such that when either

x^{p}

or

x^{q}

are input to

A, A

goes to state

s_{m}

. Now, by supposition,

A

accepts the string

x^{p} y^{p}

. This means that after

p x^{\prime}

's have been input, at which point

A

is in state

s_{m}

, inputting

p

additional b's sends

A

into an accepting state, say

s_{a}

. But that implies that inputting

x^{q} y^{p}

also sends

A

to

s_{a}

, which means that

x^{q} y^{p}

is also accepted by

A

. The reason is that after

q x

's have been input,

A

is also in state

s_{m}

, and from that point, we know that inputting

p

additional b's sends

A

to state

s_{a}

, which is an accepting state. Hence

x ^ { q } y ^ { p }

is in

L

where

p eq q

But, by supposition, all the strings in

L

have the form

x ^ { n } y ^ { n }

, which have the same number of that there is no finite-state automaton that accepts the language

L

consisting of all strings of

x ^ { \prime }

's and

y

's of the form

x ^ { n } y ^ { n }

where

n

is a positive integer.

Prove That There Is No Finite-State Automaton That Accepts the Language

Definitions: