Prove or disprove that chop(L) is a regular language

  • Thread starter Thread starter s3a
  • Start date Start date
  • Tags Tags
    Language Regular
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 3K views
s3a
Messages
828
Reaction score
8

Homework Statement


"Let L be any regular language over an alphabet Σ. Using L, we define

chop(L) = {w : ∃ x, y, z ∈ Σ∗ , xyz ∈ L, w = xz}.

Show that chop(L) is regular or give a counter-example."

Homework Equations


If an NFA that describes the language chop(L) exists, then chop(L) is a regular language.

The Attempt at a Solution


I'm trying to make a non-deterministic finite automaton (NFA), since if one can be made, then I believe that that proves that the language is regular.

Here ( https://www.docdroid.net/ZVsWIlb/nfa.pdf ) is my attempt at making such an NFA. Is that correct? If not, what's wrong with it?

Any input would be greatly appreciated!
 
Last edited:
Physics news on Phys.org
If anyone is looking at this thread, I just wanted to say that, if my attempt was incorrect, I am still trying to figure out how to perform this proof, or if my attempt was correct, I'm still looking for a confirmation.

One thing that's confusing me is whether the inputs of the NFA can only be (lone) symbols of the defined alphabet or if the inputs can also be strings.