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

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Language Regular
AI Thread Summary
If K is a regular language and M is any language, then the language L, defined as L={k | km ∈ K for some m ∈ M}, is also regular. This can be shown by taking a DFA that accepts K and modifying its accepting states to include states q where the transition function δ(q, m) leads to an accepting state for some m in M. The key distinction between the DFAs for K and L lies in the set of final states. The transition function remains the same, but the acceptance criteria change based on the presence of m in M. Thus, L is regular as it can be represented by a modified DFA derived from K.
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

Replies
3
Views
2K
Replies
1
Views
2K
Replies
3
Views
2K
Replies
1
Views
1K
Replies
6
Views
2K
Replies
1
Views
1K
Replies
18
Views
3K
Replies
24
Views
4K
Replies
5
Views
2K
Replies
8
Views
773
Back
Top