1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Sep 18 '17 at 10:33
  • $\begingroup$ It's not part of a regular expression -- it's part of the name of a regular expression, just as $i$ and $j$ are. $\endgroup$ – David Richerby Sep 18 '17 at 10:50
4
$\begingroup$

$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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sean Francis N. Ballais Sep 18 '17 at 9:22
  • $\begingroup$ $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$. $\endgroup$ – fade2black Sep 18 '17 at 9:40
  • $\begingroup$ 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). $\endgroup$ – fade2black Sep 18 '17 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.