Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Question on regular languages

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Question on regular languages

    I have seen chapters on automata in my Discrete Math books so I'm hoping this is the right forum for this question
    I have a question(2/3 of it answered). I was hoping to have what I've done so far checked and maybe get a hint on how to approach the last part.

    For two regular languages.
    a. Is LM = ML?
    b. Is it true if the alphabet is only {0,1}?
    c. Is it true if the alphabet is only {0}?

    a. No LM != ML
    let M = {abc, acb} L= {bca, bac}
    M and L are both finite, therefore M and L are regular languages
    ML = {abcbca, abcbac, acbbca, acbbac}
    LM = {bcaabc, bcaacb, bacabc, bacacb}
    here LM != ML

    b. No LM != ML if the alphabet is {0,1}
    let L = {0,00}
    let M = {1,11}
    M and L are both finite, therefore M and L are regular languages
    LM = {01,011, 001, 0011}
    ML = {10, 100, 110, 1100}
    here LM != ML

    c. if the alphabet is only {0} I would like to say that LM = ML for all languages M and L
    I'm not quite sure how to prove it though. I'm not receiving very much help on how to tackle these problems through the lectures in class so I'm kinda teaching myself.
    Last edited by restin84; October 27th 2012 at 09:47 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Question on regular languages

    Hey restin84.

    When you want to prove equality, do you just mean that every possible sentence construction in one is also in the other? Also what is the definition of a regular language?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Question on regular languages

    Quote Originally Posted by restin84 View Post
    c. if the alphabet is only {0} I would like to say that LM = ML for all languages M and L
    I agree. The fact that LM = ML holds for all L and M, not necessarily regular, as long as the alphabet is a singleton.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Question on regular languages

    Quote Originally Posted by emakarov View Post
    I agree. The fact that LM = ML holds for all L and M, not necessarily regular, as long as the alphabet is a singleton.
    The question does not necessarily ask me to prove any of these answers. Is result c something I should prove? How do you think I might go about it?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Question on regular languages

    You proved (a) and (b) by finding counterexamples. Point (c) is easy. If 0^n\in LM, then there exist l and m such that 0^n=0^l0^m, 0^l\in L and 0^m\in M. But then 0^n=0^m0^l\in ML.
    Thanks from restin84
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question (urgent) About Embeddings of Regular Graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 15th 2012, 08:21 PM
  2. Replies: 1
    Last Post: September 27th 2011, 02:42 PM
  3. How many different languages?
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 22nd 2011, 05:56 AM
  4. Languages and FSM.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 5th 2011, 01:09 PM
  5. Regular expression question
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 31st 2009, 06:05 PM

Search Tags


/mathhelpforum @mathhelpforum