HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Showing Regular Languages are closed under removal of rightmost character

Submitted by: @import:stackexchange-cs··
0
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!

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.

Context

StackExchange Computer Science Q#62298, answer score: 5

Revisions (0)

No revisions yet.