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

In summary, the conversation discusses the definition of the language chop(L) using a regular language L and poses the question of whether chop(L) is also regular. The proposed solution involves creating a non-deterministic finite automaton (NFA) to prove the regularity of chop(L). The author also provides a link to their attempted NFA and asks for feedback on its correctness. They also express confusion about whether the inputs of the NFA can only be symbols or strings of the alphabet.
  • #1
s3a
818
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
  • #2
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.
 

1. What is a regular language?

A regular language is a set of strings that can be recognized by a deterministic finite automaton (DFA). These languages are important in computer science and are used in various applications, such as programming languages and text processing.

2. How can we prove that chop(L) is a regular language?

To prove that chop(L) is a regular language, we need to show that it can be recognized by a DFA. This can be done by constructing a DFA that accepts all strings in chop(L) and rejects all other strings. If such a DFA can be constructed, then we can conclude that chop(L) is a regular language.

3. What is the difference between a regular language and a non-regular language?

A regular language can be recognized by a DFA, whereas a non-regular language cannot be recognized by any DFA. This means that regular languages have a finite number of states, while non-regular languages require an infinite number of states to be recognized.

4. Can we disprove that chop(L) is a regular language?

Yes, we can disprove that chop(L) is a regular language by showing that it cannot be recognized by any DFA. This can be done through a proof by contradiction, where we assume that chop(L) is a regular language and show that it leads to a contradiction.

5. What are some examples of regular languages?

Some examples of regular languages include:

  • Strings of 0s and 1s with an even number of 1s
  • Strings of 0s and 1s that contain the substring "01"
  • All possible strings over the alphabet {a, b}

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Back
Top