• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter s3a
  • Start date
  • #1
s3a
799
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:

Answers and Replies

  • #2
s3a
799
8
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.
 

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

Replies
0
Views
846
  • Last Post
Replies
0
Views
940
  • Last Post
Replies
1
Views
655
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
917
Replies
1
Views
1K
Replies
0
Views
3K
  • Last Post
Replies
6
Views
4K
Replies
4
Views
2K
Top