Automata and Reduced Words in the Free Group

Details Automata and Reduced Words in the Free Group Automata and Reduced Words in the Free Group

2009-10-23

arxiv.org/abs/0910.4555v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

We consider some questions about formal languages that arise when inverses of letters, words and languages are defined. The reduced representation of a language over the free monoid is its unique equivalent representation in the free group. We show that the class of regular languages is closed under taking the reduced representation, while the class of context-free languages is not. We also give an upper bound on the state complexity of the reduced representation of a regular language, and prove upper and lower bounds on the length of the shortest reducible string in a regular language. Finally we show that the set of all words which are equivalent to the words in a regular language can be nonregular, and that regular languages are not closed under taking a generalized form of the reduced representation.

Affiliated with

Also associated with

No associations

Rating

Automata and Reduced Words in the Free Group does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Automata and Reduced Words in the Free Group, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automata and Reduced Words in the Free Group will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424052