Show that if K is regular and M any language, then L is regular

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Language Regular
Click For Summary
SUMMARY

The discussion establishes that if K is a regular language, then the language L, defined as L={k | km ∈ K for some m ∈ M}, is also regular for any language M. The key approach involves utilizing a Deterministic Finite Automaton (DFA) represented as (Q, Σ, δ, q₀, F) that accepts K. By modifying the accepting states to include q ∈ Q where δ(q, m) ∈ F for some m ∈ M, L is shown to maintain regularity. This transformation confirms that the transition function of L is derived from that of K, differing only in the set of final states.

PREREQUISITES
  • Understanding of regular languages and their properties
  • Familiarity with Deterministic Finite Automata (DFA)
  • Knowledge of transition functions in automata theory
  • Basic concepts of language operations and closure properties
NEXT STEPS
  • Study the closure properties of regular languages
  • Learn about the construction of DFAs for different language operations
  • Explore the implications of modifying accepting states in DFAs
  • Investigate the relationship between regular languages and context-free languages
USEFUL FOR

The discussion is beneficial for computer science students, automata theorists, and anyone interested in formal language theory, particularly those studying the properties and transformations of regular languages.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Let $L=\{k |km \in K \text{ for some } m \in M\}$.

How can we show that if $K$ is regular and $M$ is any language, then $L$ is regular?? (Wondering)
 
Physics news on Phys.org
This is a nice problem. Take a DFA $(Q,\Sigma,\delta,q_0,F)$ that accept $K$ and make $q\in Q$ accepting iff $\delta(q,m)\in F$ for some $m\in M$. Here $\delta(q,m)$ is the extension of the transition function to strings.
 
Evgeny.Makarov said:
This is a nice problem. Take a DFA $(Q,\Sigma,\delta,q_0,F)$ that accept $K$ and make $q\in Q$ accepting iff $\delta(q,m)\in F$ for some $m\in M$. Here $\delta(q,m)$ is the extension of the transition function to strings.

So, is the transition function of $L$ the same as the transition function of $K$ ? If it stands that $\delta(q,m)\in F$ for some $m \in M$, then we make $q$ an accepting state. So the difference of the description of the two DFA's is the set of final states. Have I understood it correctly?
 
Yes, you understood it correctly.
 
Evgeny.Makarov said:
Yes, you understood it correctly.

Great! Thank you very much! (Smile)
 

Similar threads

MHB Is the language ${L}_{n}$ regular?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Proving L is not Regular using Pumping Lemma
  • · Replies 1 ·
Replies
1
Views
2K
MHB Regular and not regular Language
  • · Replies 3 ·
Replies
3
Views
2K
MHB Show that the language is regular
  • · Replies 1 ·
Replies
1
Views
2K
MHB Show Closure of Regular Languages: $L_1$ and $L_2$
  • · Replies 6 ·
Replies
6
Views
2K
MHB Convert an automaton into a regular expression
  • · Replies 1 ·
Replies
1
Views
2K
MHB Proving Regularity of $L^R$ Using DFA Construction
  • · Replies 18 ·
Replies
18
Views
3K
MHB What Do $\phi$ and $\phi'$ Mean in Regular Grammars?
  • · Replies 24 ·
Replies
24
Views
4K
MHB Proving languages are not regular.
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
4K