String generation
In computer science, string generation is the process of creating a set of strings from a collection of rules. This is an opposite process to that of parsing, which recognises a string based on some collection of rules.
Applications of string generation include test data generation, Captchas and random essay generation.
Generation methods
Methods for generating strings include:
- While a deterministic finite automaton is often used to recognize strings it can easily be changed to generate strings.
Unsolved problems
Unsolved problems in string generation include:
Note; It is an undecidable problem to decide whether a given string can be generated by a given W-grammar.
gollark: Well, the water-walking thing presumably has to either magically make him hover above the surface or effectively provide more contact area with the water, right?
gollark: Would that work? How is Jesus's water-walking thing implemented?
gollark: You can check whether the results of it are good by some other metric, but that just pushes the problem up a level.
gollark: Regarding objective morality: I don't understand how it's meant to work. Generally we consider things "true" if they're well-established by experiment and observation. I do not see how you can empirically test whether something is what you "should" do.
gollark: A kilobee is 1000 bees.
See also
- Pretty printing – another process often considered the dual of parsing.
External links
- DGL -- Data Generation Language an apparently general facility for addressing this problem
- Eli Benderski blog with a demo in Python
- Bruce McKenzie paper on a general algorithm
- Generate strings matching a regular expression
- Generate strings from a yacc grammar
- comp.compilers discussion
- random essay random essay
- Generate random C programs
- Generate random string using python
- Replacement Game user generates strings by applying replacement rules
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.