Formal Languages

This project deals with the field of formal languages, so prior knowledge in this area is helpful. To start new learners off, here is a brief and simplistic description of the basis of generative grammar. To generate sentences (here called strings) from a set of grammar rules, we require terminal and non-terminal symbols. For the following example, assume that lower-case letters are terminal symbols and upper-case letters are non-terminal symbols:

S --> a A
A --> b

Starting with the initial rule S, we observe that it can be expanded to 'a A'. Here, A is a non-terminal symbol, so the expression can be expanded further to form 'a b'. Thus, the only string generated from this set of grammar rules is 'a b'. In cases where a single rule can take on multiple variations, many different strings can then be generated.

Rule Input

In this demo, grammar rules can be input in 2 ways: in full textual input, or if you do not like typing arrows, rule-by-rule entry. Input format must be as follows:

- Rules should be specified with a non-terminal LHS, followed by -->, followed by its RHS
- Non-terminals should start with upper case letters
- The LHS of the first rule should be S
- Terminal and non-terminal symbols should be separated by a space
- An empty string is represented by a tilde (~)

Here is an example:

S-->A B
A-->~
A--> a S
B-->~
B-->b S

Here, S, A and B are non-terminal symbols, so they must start with uppercase letters. A and B both have rule variations that are empty strings, so their RHS is a ~. Symbols need not be single character, and spaces are allowed next to the arrows (no difference in result), for example:

S --> Apple Bunny
Apple --> egg Bunny
Bunny --> candy Dog
Dog --> egg
Dog --> candy Apple

Currently, the system supports only context-free grammars, so only a single non-terminal symbol is allowed on the LHS. If your language is infinite, specify the number of results you want on the first line, before the grammar rules. Otherwise, a default of 100 strings are generated. Another option provided is the random generation of a single string rather than the full grammar, obtained by using the "single instance" button.

Sound Output with Polymetric Expressions

As our program is designed to be integrated with the Polymetric Expressions program, we support a number of symbols to be used as non-terminal symbols as well, such as braces, commas and periods (full-stops). For a clearer understanding of the PE syntax, please visit their demo page. For strings generated that are consistent with this syntax, clicking on the string's hyperlink will play the corresponding sound output.

Try it out!