1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Regular Language Comparison

  1. Oct 3, 2014 #1
    1. The problem statement, all variables and given/known data

    Let truncn(L) = {w: wv exists in L, |v| = n}

    Show that trunc is regular if L is regular.

    3. The attempt at a solution

    By the definition of regular languages, L is regular if we can come up with a regular expression or a DFA for it.

    This question confuses me because what if we have a regular language L where the only string it produces is "aaa", and we take trunc8(L)? The string v can't exist if the length of wv is 3, but in this case we technically can since there are no constraints on n.
  2. jcsd
  3. Oct 7, 2014 #2

    I think that the constraints of truncn(L) prohibit us from choosing n larger than |wv| so ignore that part of my initial post.

    Can i use a DFA to prove trunc is regualr?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted