Can you obtain a string from a DFA transition table?

[erotavlas]

Taking a regular expression and converting it to a DFA with transition table, can you go backwards? I.e. take one of the rows of the table and determine what input string would be accepted for that row?

 

[Guneykan Ozgul]

If I understand your question correctly,here is my answer:
First you need to convert the DFA to GNFA (generalized nondeterministic finite automata ).A GNFA is actually special type of NFA. It contains only one accept state. There cannot be ingoing arrows to start state and outgoing arrows from accept state. Except from that there should be a transition between any two pair of states. You can look to the internet about GNFA for more information. Then you can reduce the number of states of GNFA to 2. This is possible for any GNFA. In GNFA each transition is characterized by a regular expression. So the final GNFA will have one transition which is your initial regular expression. Asfter that point you can determine the format of the string the machine accepts.

 

[erotavlas]

Will this correspond to one and only one possible string (from the total of all possible permutations of the characters) defined by the regular expression?

 

[Guneykan Ozgul]

A regular expression actually means a set of strings, so I don't understand what you mean by one possible string. If you are asking is the result a regular expression that can only define the strings that DFA recognizes, the answer is yes. The resulting expression can create one and only one set of strings which the machine recognizes. If you are asking something else I am sorry for talking about a different thing.

 

[erotavlas]

well I was wondering if the DFA can be used in any way to obtain one string (from the set of all possible strings defined by the regular expression)

 

[Guneykan Ozgul]

So, yes. Since you can obtain the regular expression, you can create a string using that regular expression. Remember that GNFA will give you only the strings that is recognized by corresponding DFA. I hope this is useful.

 

[erotavlas]

No I mean even before obtaining the regular expression. Can anything about the DFA provide you an instance of a string? Does the DFA in any way enumerate all possible string possibilities? Is there anything that does - without having to build all possibilities yourself by iterating over all the permutations of character combinations.

 

[Fooality]

So you want to enumerate the strings a finite automata matches? Intuitively that should be pretty simple. Of course that set is often infinite, and you get into issues of enumerating infinite sets, but the set should be countably infinite, so it can be done. Do I understand you right?

 

[erotavlas]

So you want to enumerate the strings a finite automata matches? Intuitively that should be pretty simple. Of course that set is often infinite, and you get into issues of enumerating infinite sets, but the set should be countably infinite, so it can be done. Do I understand you right?

Yes that's right. How is this accomplished using only the finite automata?

Also I realize some regex may represent infinite set of strings, however say we are not dealing with the infinite. Say we pose a restriction on max length that the strings can be. So we only enumerate the strings that are less than or equal to the max length.

 

[Fooality]

well, its good to visualize the Finite Automaton in terms of a state diagram: labelled circles (s1, s2, ...) connected by arrows representing state transitions, ending either in accept state or reject state. To enumerate all the accepted strings we want a function that walks through each state, forking as needed, and returning on accept. So for regex 'abc' it walks through 4 states a,b,c,accept and outputs on accept. For one like 'a(b|d)c+e' the function will fork for the OR state once, and for infinitely for c+ state. So its a recursive function. Of course you can pass a variable for recursion depth to limit string length.
Unless I am missing something big, that should work it seems.

 

[erotavlas]

well, its good to visualize the Finite Automaton in terms of a state diagram: labelled circles (s1, s2, ...) connected by arrows representing state transitions, ending either in accept state or reject state. To enumerate all the accepted strings we want a function that walks through each state, forking as needed, and returning on accept. So for regex 'abc' it walks through 4 states a,b,c,accept and outputs on accept. For one like 'a(b|d)c+e' the function will fork for the OR state once, and for infinitely for c+ state. So its a recursive function. Of course you can pass a variable for recursion depth to limit string length.
Unless I am missing something big, that should work it seems.

My question arose from learning about encryption (format preserving) and some people are using regular expressions to encrypt strings, so what they do is define a format using regular expression that the strings must follow, create a DFA or NFA for that regex, 'rank' something about the DFA table (whatever that is) from {0,1,2,...n} encrypt the number that corresponds with the input string to another number in the same set of states {0,1,2,...n}, then obtain an output string from that.

What are they ranking? How is a single string obtained from a value in the ranked set? Are they actually computing all possible combination of characters that match the regex? Or is there some special property of the DFA that magically matches with an input string and can give you an output string without manually calculating all the variations yourself (since you may end up with combinations that don't match the regex without a whole bunch of conditionals and rules to follow)?

Or maybe the DFA is required to actually obtain all the possible strings - because you can't do it easily just by iterating over all possible combination of characters (since you may end up with strings that don't match the regular expression without using complex conditionals and rules)?

 

[Fooality]

Wow, sounds like interesting stuff you're into! I'm not familiar enough to be really useful, but I can tell you that one can enumerate all the strings matched my an FA, but to pick one takes something extra. I know in ecyption probability of string appearance is important, so maybe that has something to do with the ranking system? A state transition system that includes probabilities is a Markov model... But I am really shooting in the dark here.