# What does $k$ mean in regular expressions?

From what I have learned in Introduction to Automata Theory, Languages, and Computation, regular expressions can be represented with $R^{(k)}_{ij}$.

I understand that $i$ and $j$ represent the starting state and the closing state respectively. However, I am still trying to understand the purpose of $k$.

To put it simply, what does $k$ stand for in $R^{(k)}_{ij}$?

Side note: Link to the book is here.

• You need to look at (and quote) the entire definition, not only a fragment of it. "regular expressions can be represented with..." is impossibly vague (and probably not a correct interpretation of what you've read. As a consequence, I suspect that your title has nothing to do with your question. – Raphael Sep 18 '17 at 10:33
• It's not part of a regular expression -- it's part of the name of a regular expression, just as $i$ and $j$ are. – David Richerby Sep 18 '17 at 10:50

## 1 Answer

$k$ means that if $w \in R^{k}_{ij}$ then on reading $w$, FA starting from the state $i$ enters the state $j$ and never enters a state $t$ where $t > k$ while reading input $w$. In the book, you learn from, $R^{k}_{ij}$ is defined as the set of all strings that transition the automaton $M$ from $q_i$ to $q_j$ without passing through any state higher than $q_k$.

• In a given finite automaton, is the value of $k$ the number of states the FA has? Or does this depend on what I am trying to do? – Sean Francis N. Ballais Sep 18 '17 at 9:22
• $R^{k}_{ij}$ is a recursive formula which is used to obtain a regular expression from a FA. $k$ is any number between 0 and $n$, where the $n$ is the number of states in the given FA. $R^{k}_{ij}$ can be computed iteratively starting from $k=0$ up until $k=n$. – fade2black Sep 18 '17 at 9:40
• When computing $R^{k}_{ij}$, $R^{0}_{ij}$ depends on the structure of the given FA, while for $k>0$, $R^{k}_{ij}$ is computed according to the formula (usually using tabular approach, rather than recursively for the sake of efficiency). – fade2black Sep 18 '17 at 9:44