Facebook Page
Twitter
RSS
Thanks Thanks:  0
+ Reply to Thread
Results 1 to 2 of 2
  1. MHB Apprentice
    Julio's Avatar
    Status
    Offline
    Join Date
    Feb 2014
    Posts
    67
    Thanks
    45 times
    Thanked
    12 times
    #1
    Prove that if $L$ is regular, then $L^R=\{w^R, w\in L\}$ is regular.

    Hello MHB! I need if you can help me with this problem. Thank you.

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #2
    One way is to take a regular expression $r$ that generates $L$ and construct an expression that generates $L^R$. It is built by recursion on $r$.

    Another way is to take a DFA accepting $L$ and reverse all arrows. One also has to add a new initial state and add $\varepsilon$-transitions from it to all old accepting states.

Similar Threads

  1. The language is also regular
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 18
    Last Post: August 17th, 2016, 14:20
  2. Regular and not regular Language
    By mathmari in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 3
    Last Post: March 10th, 2015, 06:28
  3. Show that if K is regular and M any language, then L is regular
    By mathmari in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 4
    Last Post: March 9th, 2015, 10:49
  4. Using Myhill-Nerode to prove a language is not regular?
    By Lolligirl in forum Computer Science
    Replies: 9
    Last Post: October 8th, 2014, 12:08
  5. Are the regular expressions the same?
    By evinda in forum Computer Science
    Replies: 2
    Last Post: January 29th, 2014, 15:08

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards