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

  • Thread starter Thread starter s3a
  • Start date Start date
  • Tags Tags
    Language Regular
Click For Summary
The discussion revolves around proving whether chop(L), defined as the set of strings w formed by removing the middle part of strings xyz in a regular language L, is itself a regular language. The key point is that if a non-deterministic finite automaton (NFA) can be constructed for chop(L), it would demonstrate that chop(L) is regular. The user seeks feedback on their NFA attempt and clarification on whether the NFA inputs should be single symbols or strings from the alphabet. The conversation highlights the importance of understanding the structure of regular languages and the properties of NFAs in this context. Ultimately, the user is looking for guidance on their proof process and NFA correctness.
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.
 

Similar threads

Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
1K
Replies
1
Views
4K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 6 ·
Replies
6
Views
4K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 18 ·
Replies
18
Views
3K
  • · Replies 1 ·
Replies
1
Views
1K