String generation

This article does not cite any sources. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (December 2011) (Learn how and when to remove this template message)

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 . (December 2011)

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.

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
• random essay random essay
• Generate random C programs
• Generate random string using python
• Replacement Game user generates strings by applying replacement rules

This computer science article is a stub. You can help Wikipedia by .

• v
• t