Is this possible using Homomorphisms?
Craig Sanders
I'm relatively new to the area of Computational Theory, so I hope I have
posted this message to the correct list!
I have a problem where L is a Regular Language which is defined over the set
{a,b,c}. I want to define a new language, say M, which is defined by
deleting from L, all of the strings that don't contain the symbol c, and
then deleting from the resulting strings, the first c and everything that
follows it. My question is, is it possible to accomplish this using
Homomorphisms, and if so, what would the Homomorphisms be for each of the
two steps?
So for example, say a simplified version of L contained only the following
handful of strings ;
L = {a,b,aa,ab,ac,ba,bb,bc,ca,cb,cc}
After Step 1, the result should be as follows, (all strings that don't
contain a c have been removed) ;
L = {ac,bc,ca,cb,cc}
After Step 2, the result should be as follows, (everything from the first c
onwards and including the first c, has been deleted from each of the
strings) ;
L = {a,b}
Any help on this matter would be most appreciated.
Thankyou.
- Craig Sanders
Kent Paul Dolan
> I'm relatively new to the area of Computational
> Theory, so I hope I have posted this message to
> the correct list!
Your query is properly posted to "comp.theory". The
current newsgroup, comp.theory.cell-automata, is
(roughly) about stepwise transition rules running in
parallel on all cells of a regular grid in n-space,
with the new cell "value" for each cell at each step
derived from the value of the cell, and from the
values of some well defined set of neighbor cells,
at the prior step.
The question you are asking is about _formal
language theory_, and is related (vaguely) to finite
automata theory, which don't have their own
newsgroups, but are instead discussed in
comp.theory, and a fairly major topic there.
HTH
xanthian.