I want to prove regularity of a language that contains a known regular language $L$ using an NFA.

Say the transition function of the automation that accepts $L$ is $f$.

In my new transition function, is there a limitation on composition of $f$? For example, can I make the following transition in the new function?

$$f'(q_i ,\sigma)=f(f(f(q_i, \sigma))))$$

If not, why?

  • $\begingroup$ Almost. You could, for instance, define $f'(q_i,\sigma)=f(f(f(q_i,\sigma),\sigma),\sigma)$. $\endgroup$ – Rick Decker Nov 15 '17 at 14:10
  • $\begingroup$ "a language that contains a known regular language L" -- as in set inclusion? How do you get from there to composing transition functions? What's the idea behind this construction? $\endgroup$ – Raphael Nov 15 '17 at 16:24

You can define the transition function of an automaton to be whatever you want, as long as it's a function of the appropriate type, i.e., $Q\times\Sigma\to Q$ fora DFA and $Q\times\Sigma\to 2^Q$ for an NFA.

However, the composition you've attempted doesn't actually make sense. Since $f$ is the transition function of an NFA, it has type $Q\times\Sigma\to 2^Q$. As such, you can't write $f(f(q_i,\sigma))$, since the argument of the outer application of $f$ is some subset of $Q$, whereas there are supposed to be two arguments: an element of $Q$ and a symbol from the alphabet. So, for a double-composition, you probably need to write something like $$\bigcup\{f(q,\sigma)\mid q\in f(q_i,\sigma)\}\,.$$ You can try to work out the triple-composition yourself.

But are you sure you want to do that? You're defining an automaton that says "Every time I read the character $\sigma$, I will do whatever the original automaton would have done if it read three $\sigma$s." As I said, you can make your automaton do whatever you want, but I'd be interested to know the context that makes this a sensible thing to do.

| cite | improve this answer | |
  • $\begingroup$ The example I gave isn't what I want to use, I just checked if this kind of operation is correct. I need something similar to prove the regularity of the following language where L is regular. My idea is to activate f on the first x, then from that state, activate it on each of the letters in the alphabet, and then from that group activate it again on each letter in the alphabet, then receive the next x input and so on. I need the composition in order to put the results of the first activation of the function (the state) as parameters for the next one. $\endgroup$ – Eloo Nov 15 '17 at 21:08

The transition function of a DFA is $Q \times \Sigma \rightarrow Q$. aka a function that takes a State and a symbol and outputs another state.

As long as that is valid it doesn't matter how it is built.

For example the DFA built from an NFA. There each state of the DFA is a subset of the states of the NFA and the transition function returns the union of the output of the NFA's transition function applied to each state in the input subset.

| cite | improve this answer | |

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.