patternMinor
Showing Regular Languages are closed under removal of rightmost character
Viewed 0 times
removalshowinglanguagesareregularclosedcharacterunderrightmost
Problem
"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular."
I tried going by closure properties of regular languages but got nowhere.. I said L' = {x| y is in L and xa = y, for some a in the alphabet} and didn't really know where to go from there... I also tried to argue that since L is a regular language, it can be expressed by some regex..and I wanted to show by cases that we can form a new regex by omitting the last unit of regex? But that seemed flawed. I also tried creating a skeleton dfa for L and just changing the set of accepting states to the states that transition into the previous final states.. I feel like there is a gap in my knowledge and would really appreciate it if someone could not only help me figure out the solution but also give me some advice on how to approach such problems and fill the gaps in my knowledge!
I tried going by closure properties of regular languages but got nowhere.. I said L' = {x| y is in L and xa = y, for some a in the alphabet} and didn't really know where to go from there... I also tried to argue that since L is a regular language, it can be expressed by some regex..and I wanted to show by cases that we can form a new regex by omitting the last unit of regex? But that seemed flawed. I also tried creating a skeleton dfa for L and just changing the set of accepting states to the states that transition into the previous final states.. I feel like there is a gap in my knowledge and would really appreciate it if someone could not only help me figure out the solution but also give me some advice on how to approach such problems and fill the gaps in my knowledge!
Solution
This is just a special case of right quotient. Specifically, for a language $L$ over an alphabet $\Sigma$, this is $L / \Sigma$.
Many textbooks and course notes contain proof of regular languages' closure under right quotient. For example, here, on page 10.
Many textbooks and course notes contain proof of regular languages' closure under right quotient. For example, here, on page 10.
Context
StackExchange Computer Science Q#62298, answer score: 5
Revisions (0)
No revisions yet.