← All problems
Unverified

Left quotient operator on regular expressions

Given two regular languages L1L_1 and L2L_2, we can define the left language quotient operations as L2\lL1:={v ∣ ∃u,uv∈L1∧u∈L2}L_2\backslash_lL_1 := \{ v \ \vert \ \exists u, uv \in L_1 \land u \in L_2 \}. The Brzozowski derivative is a special case of the left quotient by a singleton language: {c}\lL1:={v ∣ cv∈L1}\{c\}\backslash_lL_1 := \{ v \ \vert \ cv \in L_1 \}. This leads to the following question: is there a purely inductive definition of the left quotient operation on regular expressions? i.e. a function f:RE×RE→REf : RE \times RE \to RE s.t. L(f(R2,R1))=L(R2)\lL(R1)\mathcal{L}(f(R_2,R_1))=\mathcal{L}(R_2)\backslash_l\mathcal{L}(R_1).

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu