Re: Is it possible to accomplish this using Homomorphisms?

On Mar 24, 7:17 pm, "Craig Sanders" <cms...@xxxxxxxxxxxxxxxxxxxxx>
wrote:
Hello all.

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?

Homomorphisms (in the context of formal language
theory) replace letters with words, so neither
of the two things you want to do can be done
using just homomorphisms.

If you have a language L over an alphabet A,
and you want the sublanguage L' of those words
in L whichcontain the letter c from A, you
can simply intersect L with the regular
language A*cA*, so that

L' = L intersect A*cA*.

The second operation is a bit more complicated.

-- m
.

Relevant Pages

  • help with problems on computability needed!!
    ... retake this course on computational theory and complexity... ... First question: ... We say that a language L is decidable with lag t if there exists a TM M ...
    (comp.theory)
  • Re: TCL cant do as much as Perl
    ... in Computational Theory it does not. ... I've never heard the question "which is a better language" asked outside of Theory of Computation college classes where the appropriate answer was "they're both provably identical, ... Darren New / San Diego, CA, USA Indications you're in trouble, #37: Your accountant charges you interest for not paying bills for which you already have the canceled checks back. ...
    (comp.lang.tcl)