CODEWITHSUNDEEP
regexdfa
Chris
Chris

Reputation: 807

Creating a DFA from : x^a y^b x^a

I have no idea how to create a Deterministic Finite Automata from the language:

x^a y^b x^a  where a,b >=0

The main issue I have is how to represent a backreference (the second x^a). These two x's should be as frequent as each other.

How do I write a DFA to accomodate this?

From what I understand, I can terminate at initial state, have zero or more x's and terminate, have zero or more y's then terminate, or zero or x's and terminate, or some or all of them and then terminate.

This is homework so it would be appreciated if an explanation is included, if necessary. Thanks.

Upvotes: 0

Views: 65

Answers (1)

isekaijin
isekaijin

Reputation: 19772

Finite automata recognize exactly the class of regular languages, and your language isn't regular, for more or less the same reasons the Dyck language isn't. You can prove it using the pumping lemma for regular languages. Since this is homework, I won't take away from you the excitement of actually coming up with the proof.

Upvotes: 2

Related Questions