String generation
Jump to navigation
Jump to search
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
![]() | This section needs expansion. You can help by adding to it. (December 2011) |
Unsolved problems in string generation include:
It is an undecidable problem to decide whether a given string can be generated by a given W-grammar.
See also
- Pretty printing – another process often considered the dual of parsing.[citation needed]
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
- Generate random C programs
- Generate random string using python
- Replacement Game user generates strings by applying replacement rules
Categories:
- Articles lacking sources from December 2011
- All articles lacking sources
- Articles to be expanded from December 2011
- All articles to be expanded
- Articles using small message boxes
- All articles with unsourced statements
- Articles with unsourced statements from February 2012
- Algorithms on strings
- Parsing
- All stub articles
- Computer science stubs