4 ms·
Reminds me of what my TA showed us in undergrad. If I remember correctly, it went like this: Consider the regex A: Aa | ϵ, where ϵ denotes the empty string. Wh
by dataflow 8y ago
Reminds me of what my TA showed us in undergrad. If I remember correctly, it went like this:
Consider the regex A: Aa | ϵ, where ϵ denotes the empty string. What strings does it generate?
To solve, rewrite it as A = Aa + ϵ, then find its Taylor series and you're done:
A = ϵ / (ϵ - a) = ϵ + a + aa + aaa + ...
- saagarjha 8y agoNitpick: A is a production, not a regex, which would be something like a*. Edit: I meant "A: Aa | ε" instead of "A"
- mehrdadn 8y agoNo... the production is the entire rule, so "A: Aa" and "A: ϵ" are the productions.
- saagarjha 8y agoMy formal automata class might have used non-standard terminology, but what I was taught was that while A: Aa and A: ε are productions, A: Aa | ε is just a shorthand to combine the two. Since there is only one start variable, A: Aa | ε is the entire grammar as well. a* is the regular expression representing the language for this grammar.
- mehrdadn 8y ago> but what I was taught was that while A: Aa and A: ε are productions Huh? This is the exactly what I also just said, in response to the different claim you made above, which was that the production is merely "A" rather that "A: Aa" or "A: ε". If you're claiming they are somehow equal (which they clearly are not... one is a symbol and the other is a rule mapping that symbol to a sentential form) then I'm confused how you think A and a* were any less equal to begin with...
- emilfihlman 8y agoA=Aa+e A-Aa=e A(1-a)=e A=e/(1-a) not e/(e-a)
- dataflow 8y agoNope, I'm pretty sure it's not wrong. I believe ϵ is the multiplicative identity ("1") here. Note that ϵ is the empty string, and concatenating it with anything results in the same thing, so Aϵ = A. Hence we have Aϵ - Aa = A(ϵ - a) = ϵ.