1

Consider the following theorem:
Theorem: If L=L(A) for some DFA A, then there is a regular expression R such that L=L(R)

Proof: Let A's states be: {1,2,3,....n} for some integer n. Let $ R^k_{ij}$ be the name of regular expression whose language is the set of path from state i to state j in A, and it's intermediary nodes do not have number greater than k.

Basis: For k = 0, there are no intermediary nodes. So, when i != j, if the symbol for transition is a, then:
a) if there is no such symbol a, then: $ R^0_{ij} = \{\} $
b) if there is one then: $ R^k_{ij} = a$
c) if there are symbols $\ a_1, a_2, ... a_k$ then $ R^0_{ij} = a_1+a_2...+a_k$

Induction: Suppose there is a path from state i to j that goes through no higher state than k. There are two possible cases.

1) The path does not go through state k at all. In this case, the label of the path is in the language of: $ R^{(k-1)}_{ij}$
#so far so good- no confusion upto this point

The biggest part of confusion is here in this statement no. 2
2) The path goes through state k at least once. It may be from i to k, k to k multiple times, and from k to j OR it may be from i to k and k to j. So, the regular expression would be: $ R^{k-1}_{ik}.(R^{k-1}_{kk})^*.R^{k-1}_{kj}$ So, combining the regular expressions from 1 and 2 we get the regular expression from the automaton as: $$ R^k_{ij} = R^{k-1}_{ij} + R^{k-1}_{ik}.(R^{k-1}_{kk})^*.R^{k-1}_{kj}$$

The notation of $R^{k}_{ij}$ is that it should have no intermediary nodes greater than k, put another way, it may have less than *or equal to * k numbered states. So, in induction point number 2, we have the case where the intermediary nodes are allowed to touch k, though not pass higher than k. As it states, the path goes through k at least once, and yet, The regular expression is given as: $ R^{k-1}_{ik}.(R^{k-1}_{kk})^*.R^{k-1}_{kj}$, in my opinion it should rather be: $ R^{k}_{ik}.(R^{k}_{kk})^*.R^{k}_{kj}$. Where am I understanding this wrong, because, the former expression given in the proof, does not even touch k, where as my given expression would touch k.

Again, I could think it could be some print error given in the book, but all exercises have been based on this formula, so it should be accurate.

bzal
  • 560

1 Answers1

2

Your suggested regular expression is correct, in the sense that it is equal to $R_{ij}^k$, but it's not very useful, because to construct $R_{kk}^k$ for example, you already need to know what $R_{kk}^k$ is!

The point of the proof is to induct on $k$, and to do this we cleverly define $R_{ij}^k$ in terms of expressions $R_{mn}^l$ where $l<k$, and we assume we already know how to construct such expressions. Otherwise we would have a circular definition.

Daniel Mroz
  • 2,346
  • so how does saying, "The path goes through state k at least once. " in the proof make sense? – bzal Aug 01 '18 at 11:32
  • Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$. – Daniel Mroz Aug 01 '18 at 11:50
  • I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there? – bzal Aug 01 '18 at 11:54
  • Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (https://pasteboard.co/Hx9p26G.jpg) – bzal Aug 01 '18 at 11:56
  • @bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_{ik}^{k-1}$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_{kk}^{k-1})^* R_{kj}^{k-1}$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work. – Daniel Mroz Aug 01 '18 at 12:06
  • In your diagram $R_{14}^3$ is empty, because there are no paths that go from $1$ to $4$ without passing through $3$ as an intermediate state. Also, the equation is incorrect. It should be $R_{14}^4 = R_{14}^3 + R_{13}^3 \cdot (R_{33}^3)^* \cdot R_{34}^3$. – Daniel Mroz Aug 01 '18 at 12:08
  • The value of k is 4, but you're replacing k with 3 in the subscripts of R. The formula above doesn't have subscripts k-1 in R. – bzal Aug 01 '18 at 12:17
  • do you mean, they may not contain k as an intermediary state, but they may start or end with the state k? – bzal Aug 01 '18 at 12:22
  • @bzal Ah, my mistake, you're correct. Although it still should be $R_{14}^3 + R_{14}^3 \cdot (R_{44}^3)^* \cdot R_{44}^3$ :) And yes, that is what I mean. $R_{ij}^k$ denotes the paths that do not touch $k$ unless k=i and they start at k, or k=j and they end at k (or both). – Daniel Mroz Aug 01 '18 at 12:24
  • why is k even here? Why is the notion of k not being in the intermediary node necessary to derive regular expression if we just want to go from i to j? – bzal Aug 01 '18 at 12:31
  • @bzal Introducing the $k$ does seem arbitrary and like it's been pulled out of a hat, but it's helpful because it gives us something useful to induct on. Directly finding a regular expression for paths from $i$ to $j$ is not easy, where would you even start? But the notion of decomposing a hard problem into subproblems, and inductively reconstituting a solution is a strategy that comes up frequently in mathematics and computer science. Introducing $k$ lets us do that in a systematic way. Ultimately I don't know if there's a more satisfying answer to "why introduce $k$" than "because it works". – Daniel Mroz Aug 01 '18 at 12:41
  • Yeah, that's correct. And I think I could explain why $R^4_{12}$ means path from 1 to 4 not exceeding 4, but.... one last diagram..... – bzal Aug 01 '18 at 12:44
  • about you said earlier about the starting and ending states. Suppose, $R^4_{1,4} = R^3_{1,4} + R^3_{1,4}.(R^3_{3,3})^*.R^3_{3,3}$ and suppose all the required paths also exist. Now, $R^3_{1,4}$ would include all the paths from 1 to 4 that does not include the state 3, suppose x is the alphabet that is directly leading to the final state 4, so would x be in the $R^3_{1,4}$? Considering that 4 is a state greater than 3. (Didn't know what the diagram would look like, hope the explanation is clear though.) – bzal Aug 01 '18 at 12:55