Menu
Welcome to XWizard: The Online Informatics Toolbox

XWizard usage guidelines

XWizard (eXercise Wizard) is a tool for creating and visualizing mathematical objects of various types for the purpose of both learning and teaching. Among the supported object types are Turing machines, finite state machines, pushdown automata, Chomsky grammars, several types of search trees and others. In order to define a certain object, a script with an individual syntax (as defined below) has to be input into the script field on the main page. Once created, algorithms such as automaton minimization, syntax parsing and many more can be applied to the objects by using conversion methods given as buttons. More precisely, each of these algorithms transforms the script that underlies the current object into another script representing a new object which, in turn, changes the output into the new object's graph. Strictly speaking, scripts are the sole underlying control mechanism, so providing an appropriate script can always substitute for clicking any of the buttons. On the other hand, many operations can be performed by just using the graphical interface (buttons etc.) and not caring about the script.

You can use the examples on the main page as a starting point for creating a script of a specific type. If you have trouble with a script, read the help pages below or click the   discuss this script   link below the script area to get help in the community.

XWizard was originally developed for the → KIT course → Info II, but by now it includes non-Info II script types as well. Beyond this web version, a desktop version called PDF XWizard with more functions and no restrictions regarding script size or calculation time is → available for free from sourceforge.

If you're interested in joining the XWizard development team, for example if you want to implement your own script types, please send an email to → lukas.koenig@kit.edu.

Exercise mode

Besides the regular mode where all conversion methods are available and you are free to work with whatever types of scripts you desire, XWizard can be run in another mode called exercise mode. There, a question is posed that you are supposed to answer. In this mode, some of the conversion methods might be hidden, and you can only use the remaining ones to get to the solution. Furthermore, an exercise script can be encrypted (completely or partially) to blur its content and preserve for you the fun of solving it yourself (as the solution is encoded in the script). Once an exercise is answered correctly, you receive a bonus badge (this is a secret word), and XWizard returns to regular mode.

Note that you are allowed to generate your own individual exercises. For this, use the button   create exercise from this script  . To archive and share exercises (or any other scripts), you can convert them into a URL by using the button   url to this script.   To avoid very long URLs, exercises and (nearly) all other scripts can be encoded as a short URL by using the button   short url to this script...  .

Technicalities

XWizard works with complex objects which may have uncomputable properties (particularly Grammars and Turing machines have many such properties). Therefore, some requests that might run into very long-lasting or even infinite loops cannot be rejected before-hand as it is not possible to recognize them. XWizard will therefore run the according algorithms anyway, and break up the loops first when they consume too much time or space. In many of these cases, an error message will show you that something went wrong, in some rare cases the requested operation will just not be performed. In any case (at least as far as we know), XWizard will keep running correctly within its designated target space, i.e., it will remain stable. The error messages might be made a little nicer in future, but they are in any case not a sign of instability as the problem root itself cannot be solved. (If you do experience more serious problems, however, such as the site not reacting anymore or showing an HTML error or Java exception, please let us know → here.)

Cookies: XWizard uses a single cookie, which is just a random integer number, to recognize you when you come back the next time. If you disallow cookies, personal settings such as language, mode etc. might not work correctly.

Known bug 1: You may use the   back   button of your browser, but if you immediately afterwards try downloading the PDF, it will not be available. Click   draw!   to recreate the PDF, then click the   download pdf   link. Note that your browser should allow cookies for the PDF download to work correctly.

Known bug 2: If the current script has been generated using a conversion method the short URL cannot be generated directly. Click the   draw!   button before creating the short URL.

Help for 'FSM'

A finite-state machine (FSM; also just state machine or finite-state automaton), is a mathematical model of computation. Apart from its applications in theoretical computer science, it is practically used to design both computer programs and sequential logic circuits. An FSM is conceived as an abstract machine that is in one state (called the current state) out of a finite number of possible states at a time. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states and the triggering condition for each transition.

Note that the overall current state of a non-deterministic FSM can consist of several states or no state at all. However, in essence the above description still applies in this case, as any subset of the set of states of a non-deterministic FSM can be seen as a single state in an equivalent deterministic FSM. (Cf. the → power set construction procedure to make a non-deterministic FSM deterministic.)

An FSM-like behavior is typical to many real-world appliances which perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines which dispense products when the proper combination of coins is deposited, elevators which drop riders off at upper floors before going down, traffic lights which change sequence when cars are waiting, and combination locks which require the input of combination numbers in the proper order. Find more details regarding FSMs → here.

Usage in XWizard:

  • Start a script with fsm: to indicate an FSM script.
  • Provide a list of transitions, each having the form: (s0, a) => s1; (meaning: from state s0, if reading a, go to state s1).
  • The list of states as well as the symbols of the input alphabet are not given explicitly. When reading a transition, the given states (s0, s1 in the above example) as well as the input symbol (a in the above example) are assumed to be part of the FSM.
  • The initial state (s0) and the list of final states (F) have to be defined in the declarations area (click gray conversion button   format script   or   add declarations to script   to add declarations to a script).
  • By clicking on   simulate one step  , you can provide an input word which the FSM is simulated on by repeatedly clicking the same button. (You can accomplish the same by entering an input word and a simulateToStep value into the declarations area.)
  • If you define a deterministic FSM, you can click   minimize   to create an equivalent minimal FSM.
  • In this case, you can also show the minimization table by clicking   show minimization table  .
  • If you define a non-deterministic FSM, you can create an equivalent deterministic FSM by clicking   determinize  .
  • For any FSM you can generate the   minimization chain   which gives information about the determinization and minimization process.
  • You can convert the FSM into an equivalent pushdown automaton (  pda  ), a turing machine (  tm  ), a right-linear grammar (  rl grammar  ) or a regular expression (  regex  ) by clicking on the according buttons.

Conversion
methods
Conversion into Randomize...
X

Create new random FSM. Please enter parameters:

arg0: (int: The number of states in the random target automaton.)
arg1: (boolean: If set to true, the resulting automaton will be deterministic.)

Randomize (seed)...
X

Create new random FSM by providing a fixed random seed. Please enter parameters:

arg0: (int: The number of states in the random target automaton.)
arg1: (boolean: If set to true, the resulting automaton will be deterministic.)
arg2: (long: The random seed.)

Simulate one step...
X

Simulate for one step according to given input string Please enter parameters:

arg0: (String: Enter an input word to simulate.)

For teachers Animate FSM simulation...
X

Create a standard animation simulating a given input. Please enter parameters:

arg0: (String: Enter an input word to simulate.)

Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!




Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'PDA'

In computer science, a pushdown automaton (PDA) is a computational model that employs a tape accessible in 'Last-In-First-Out' manner, i.e., a → stack. The term pushdown refers to the image that the stack is being 'pushed down' like a tray dispenser at a cafeteria, since the operations work on the top element only, and the other elements remain untouched until reaching the top.

In terms of computational power, PDAs are more capable than finite-state machines but less capable than Turing machines. More precisely, deterministic PDAs can recognize all deterministic context-free languages while nondeterministic PDAs can recognize all context-free languages. Mainly the former are frequently applied in the area of parser generation. Continue reading → here to get more general information.

A PDA scans an input word from left to right while switching between a finite number of states. Additionally, the PDA can store in each step an arbitrary number of symbols on the stack (push); of these symbols, only the top-most one is read and removed in each step (pop). Accordingly, a PDA transition maps a tuple containing a state, an input symbol (read on the input tape) and a stack symbol (popped from the stack) onto a target state and a sequence of symbols to be pushed to the stack. A PDA accepts an input if it reaches a final state after processing the complete input.

Usage in XWizard:

  • Start a script with pda: to indicate a PDA script.
  • Provide a list of transitions like this: (s0, a, b) => (s1, ab); (meaning: from state s0, if reading a on the tape and popping b from the stack, go to state s1 and push ab to the stack; as b has been popped before, this means that, in effect, b remains on the stack, and a is pushed on top of it).
  • The output of a PDA script is a sequence (or tree in the non-deterministic case) of computation steps performed on a given word.
  • The input word (several allowed in deterministic case) to process is given as inputs in the declarations area (click gray conversion button   format script   or   add declarations to script   to add declarations to a script).
  • The initial state s0, the list of final states F and the special stack symbol (denoting the bottom of the stack) kSymb are also defined in the declarations area.
  • Clicking button   pda definition   switches to Latex mode and shows the definition of the PDA.
  • For a deterministic PDA, button   calculation steps   switches to a nicer depiction of the computation trace in Latex mode.

Conversion
methods
For teachers Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!




Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'Turing'

A Turing machine (TM) is a computational model (automaton) from theoretical computer science. It is a hypothetical device that can manipulate symbols on a one-dimensional tape according to a table of rules (transitions). In essence, it can be imagined as a finite-state machine with the following alterations:

  • The tape is infinite to both the left and the right, containing at the beginning the input word surrounded by infinite sequences of a blank symbol *. For example: ...****abaabaabb****...
  • The head can both read and write symbols, i.e., replace the symbol it reads by another one.
  • The head can move in both directions or stand still.
  • The transition function is not total, meaning that there may be states which for certain read symbols do not have a following state. In this case (and only in this case), the TM calculation is terminated (the TM halts).
A TM is said to compute a function which is defined by mapping the input word (for all possible input words) onto the corresponding word written on the tape after halting, i.e., the word generated during the computation process. Furthermore, a TM is said to accept all input words that cause the machine to halt in a final state. The set of these words is called the language of the TM. As not all TMs halt for all input words, their computed functions do not have to be total. Despite its simplicity, a TM can be adapted to simulate the logic of any computer algorithm in terms of computing the same function as the corresponding program does. For further information look → here.

A TM is non-deterministic if more than one transition exists for a state and a corresponding input symbol. In this case the TM considers all possibilities simultaneously leading to a computation tree (rather than a computation sequence). A non-deterministic TM accepts all input words that lead to a computation tree with at least one branch ending in a final state.

Usage in XWizard:

  • Start a script with turing: to indicate a TM script.
  • Rather than using a table, XWizard excepts a list of transitions of the form: (s0, a) => (s1, b, R); (meaning: from state s0, if reading a, go to state s1, write symbol b on the tape field where the head resides, and position the head one field to the right; also allowed: L for left and N for neutral, i.e., no movement).
  • The list of states as well as the symbols of the input and tape alphabets are not given explicitly. When reading a transition, the given states (s0, s1 in the above example) as well as the tape symbols (a, b in the above example) are assumed to be part of the TM.
  • The initial state (s0), the list of final states (F) and the blank symbol (*) have to be defined in the declarations area (click gray conversion button   format script   or   add declarations to script   to add declarations to a script).
  • The default ouput graph of a TM script is a sequence of tapes denoting the trace of a computation beginning with a certain input word. The input word also has to be defined in the declarations area. For this, the variable inputs can be set to one or several strings denoting one or several input words. In the latter case, several computation traces are depicted at once. Note that for non-deterministic TMs only one input word is allowed. The output is a computation tree rather than a sequence.
  • As TMs can run indefinitely, the variable runStepsScript defines an upper bound for computation steps to simulate.
  • Setting the variable shortTrace to true lets XWizard hide computation steps which represent the same action as the preceding step.
  • Other than the default output, a TM script provides conversion methods into Latex scripts to show the transition table and the (visually nicer) computation trace, respectively.
  • Furthermore, a random TM can be generated by clicking   random busy beaver  . According to a user-defined number of states |S| and a number of trials t, the algorithm generates t random TMs with |S| states and input word *. The ouput script is the one of the t TMs which has the most '1' symbols in the computed word, i.e., the 'busiest' of all the generated machines. Cf. the definition of → Busy Beavers.

Conversion
methods
Conversion into Random Busy Beaver...
X

Create new random 'Busy Beaver'-like Turing machine Please enter parameters:

arg0: (int: The number of states which the → Busy Beaver-like Turing machine is supposed to have.)
arg1: (int: Creating a Busy Beaver for any given number of states is incomputable. Therefore, this method creates a number of random Turing machines and returns the 'busiest'. This number is specified here.)

For teachers Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!




Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'Grammar'

In formal language theory (studied both in theoretical computer science and linguistics), a Chomsky grammar, formal grammar or simply grammar is essentially a set of production rules for strings, i.e., sequences of symbols. The rules describe how to construct strings over a given alphabet that are valid, as opposed to unconstractable, i.e., invalid strings. The set of valid strings is called the (formal) language of the grammar.Therefore, grammars are usually thought of as language generators.

However, grammars can also be used as the basis for recognizers, i.e., programs for determining whether a given string belongs to a grammar's language or not. For this purpose, the grammar is processed by the classic recognizing formalism: an automaton (which is basically a computer program). In addition to plain recognizing, a grammar can be used to parse a given string if it is in the grammar's language. Parsing provides information about how the string is constructed by the grammar. For grammars of Chomsky type 2, parsing is efficiently possible (for example by using an → Earley parser) and the result is a → parse tree or syntax tree. Due to these properties, grammars are particularly useful as a basis for programming languages.

Word generation: A grammar's rules define a set of rewriting operations on strings, such as string => another-string, along with a start symbol S. Beginning with the set {S} (containing only the start symbol), all strings are added to the set that can be generated by taking a string from the set and replacing a substring that matches the left side of a rule with its right side. The language of the grammar is defined to be a subset of the resulting set which contains only terminal words, i.e., words containing only symbols from a subset of the underlying alphabet called the set of terminal symbols T. The remaining symbols are called the set of non-terminal symbols N. More information on grammars can be found → here.

Usage in XWizard:

  • Start a script with the preamble grammar: to indicate a regular grammar script. This will show a complete generation tree, i.e., all words that can be generated from S up to a certain depth. By adding parse(a, a, b, b, a, b)--0 to the preamble (right before the colon), parse mode is activated showing the parse tree for the word a, a, b, b, a, b.
  • To switch between the two modes, the buttons   complete tree   and   parse single word   can be used as well.
  • If a word can be parsed in different ways, the trees can be toggled by clicking the   toggle...   button or changing the number in --0.
  • Note that all parse trees are shown, not only those with the start symbol as root.
  • The rules are given by a list of elements such as A, S => b, A, A, c.
  • In grammar scripts a symbol can consist of several characters, therefore, symbols are spearated by commas.
  • Both the left side and the right side of a rule can consist of more than one symbol (cf. Chomsky hierarchy).
  • By convention, uppercase letters are usually used for nonterminals, lowercase letters for terminals. Nevertheless, nonterminals, terminals and the start symbol can be given explicitly (and by disobeying the convention if desired) in the declarations area as N, T, S (click gray conversion button   format script   or   add declarations to script   to add declarations to a script).
  • In regular mode, the variables maxdepth, maxLengthWords, cutNonTerminalBranches, cutTerminalDoubleBranches can be used to restrict the size of the generated tree. The first two do what their name tells. The last two hide all nonterminal branches and all terminal branches if they lead to an already generated word, respectively.
  • Using conversion methods, the grammar can be made   epsilon-free  , transformed into   chomsky nf  ,   greibach nf   or   kuroda nf   (for type-1 grammars), or   randomize  -d.
  • An equivalent push-down automaton can be generated by clicking   pda  .
  • By clicking   display mode   different views of the grammar can be shown. This includes the grammar definition, a parsing tree and derivation chains.
  • Setting multiLetterSymbolsHaveIndex=true leads to displaying symbols with more than one character by subscripting all characters following the first.
Note that parsing and most conversion methods require type-2 grammars. Parse trees do not exist for non-type-2 grammars, and deciding if a word is in such a grammar's language is at least NP-hard; Chomsky and Greibach normal forms do not exist for non-type-2 grammars as well, and making such a grammar epsilon-free is harder. Possibly, some conversion methods for non-type-2 grammars will be added in future. Kuroda NF has been added as a first start.

Conversion
methods
Conversion into Parse single word...
X

Parse single word and toggle to syntax tree view Please enter parameters:

arg0: (String: Enter a word to create a parse tree from. If it includes multi-character symbols, use commas to separate them.)

For teachers Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!




Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'RegularExpression'

In theoretical computer science and formal language theory, a Regular expression (RE or regex) is an operational method to define a formal language. For an alphabet E, an RE α defines (by using basic operations on sets) how characters from E can be combined to sequences of characters, i.e., words in the language L(α). There, α is a valid RE if

  • α = or α = e for e ∈ E or
  • α = (α1 + α2) (union) or
  • α = (α1 · α2) (concatenation) or
  • α = (α1)* (iteration or 'Kleene's operation')
for valid REs α1, α2. The language of an RE is given by recursively evaluating the above-defined patterns as follows:
  • L() = , L(e) = {e},
  • L((α1 + α2)) = L(α1) ∪ L(α2)
  • L((α1 · α2)) = L(α1) L(α2) where L1 L2 = {w1w2 | w1 ∈ L1, w2 ∈ L2}, and
  • L((α1)*) = i ∈ 0 L(α1)i.
For example, ((a · b))* is a regular expression over the alphabet E = {a, b} which defines the language {λ, ab, abab, ababab, ...}. Note, however, that parentheses can be omitted if the RE can be interpreted correctly by evaluating * before · before +, and that · is usually not written. Thus, the above RE can be written as (ab)* as well. Note furthermore, that by definition the empty word λ can be expressed by the RE: *

The set of languages which can be defined by REs is the same that can be recognized by a finite state machine or constructed by a right-linear grammar. Therefore, there are algorithms to construct for any RE an equivalent finite state machine and vice versa (the same is true for right-linear grammars).

In practice, REs are mainly used in pattern matching with strings, or string matching, i.e. 'find and replace'-like operations. The concept arose in the 1950s, when the American mathematician Stephen Kleene (cf. 'Kleene's operation' above) formalized the description of a regular language. REs came into common use with the Unix text processing utilities ed, an editor, and grep (global regular expression print), a filtering program. REs are so useful in computing that the various systems have evolved to provide both a basic and extended standard for the grammar and syntax; modern regular expressions heavily augment the above-defined minimal set of operations. XWizard, however, doesn't.

More information regarding REs, particularly practical usage guidelines, can be found → here.

Usage in XWizard:

  • Start an RE script with regex:
  • Type a regular expression which may be abbreviated in the usual ways.
  • All lowercase letters (a, b, c, ...) and numbers (0, 1, 2, ...) are in the terminal alphabet.
  • Union is given by +, concatenation by . (but omissible), Kleene's star by *.
  • O (the uppercase letter, not the number) is the empty set , O* is (accordingly) the empty word λ.
  • The output is automatically simplified in some basic ways. To simplify the script, click   simplify (a little)  .
  • Note that minimizing an RE is PSPACE-complete, so all simplifications are merely straight-forward 'common sense' operations which will simplify the RE only to a basic extent.

Conversion
methods
For teachers Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!

Help for 'Tree234'

A 2-3-4 tree is a self-balancing data structure. Each node possesses either two, three or four children. A two node has one data element, a three node two data elements and a four node three data elements. All leaves possess the same depth. For further information see → Wikipedia.

Usage in XWizard: The tree implementation possesses two operation modes. In simple mode you simply type in a sequence of elements that are separated by spaces. These elements are inserted one by one into an empty tree, so their order from left to right defines their insertion order into the tree. Simple mode is activated by prepending simple- to the prefix tree234:.

The tree can also be defined using a script language. Please note that although some basic sanity checks are performed, the implementation does not check, whether the script defines a valid tree. (The implementation does, for example, not yet check, whether the tree is balanced or if the order of elements is correct.) A node is defined by writing all the values it contains separated by commas into brackets. A parent-child relationship between two brackets can then be established using the following mapping syntax: [p1] => [c1,c2];. It is possible to define multiple children in the same rule by separating children with pipes, i.e. [p1] => [c1,c2]|[c3];

You can either store integers, real numbers or strings in this tree. You can change the type of values in the declarations sectionby setting the variable type to a different value. Choose either integer for integers, real for real numbers, or string for characters or strings.




Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'RedBlackTree'

A red-black tree is a self-balancing binary search tree. The self-balancing property of this tree type guarantees that searching, insertion, deletion (and rebalancing) is always performed in O(log n), where n is the size of the tree. A red-black tree distinguishes between red and black nodes (indicated by red dotted and black solid lines in the PDF). A red parent node may never have red child nodes. For further information see → Wikipedia.

Usage in XWizard: The tree implementation possesses two operation modes. In simple mode you simply type in a sequence of elements that are separated by spaces. These elements are inserted one by one into an empty tree, so their order from left to right defines their insertion order into the tree. Simple mode is activated by prepending simple- to the prefix redblack:.

The tree can also be defined using a script language. Please note that although some basic sanity checks are performed, the implementation does not check, whether the script defines a valid tree. (The implementation does, for example, not yet check, whether the tree is balanced or if the order of elements is correct.) Use the syntax p => c to specify that 'p' is the parent of 'c'. p and c are placeholders for values that you want to store in the tree. To declare a node as red, prepend r: to all of its occurrences in the script.You can specify the left and the right children in one line by separating the values of the two children by a pipe, i.e.p => c1|c2

You can either store integers, real numbers or strings in this tree. You can change the type of values in the declarations sectionby setting the variable type to a different value. Choose either integer for integers, real for real numbers, or string for characters or strings.




Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'BDD'

Binary decision diagrams (BDDs) are used to represent Boolean functions in a compressed way. They are usually more efficient than other representations such as truth tables or normal forms of boolean expressions (in terms of space as well as time to calculate a value from a given tuple of Boolean input values). Unlike other compressed representations, operations can be performed directly on the compressed representation, i.e., without decompression. BDDs are constructed in a bottom-up procedure from a truth tree as shown → here.

Usage in XWizard:

  • Just write a series of 0s and 1s in the order as given in a standard truth table of the desired function to define the BDD.
  • If the length is not 2n for some n, 0s are filled in at the end.
  • If you add declarations to the script (click gray conversion button   format script   or   add declarations to script   to add declarations to a script), you can specify how many construction steps to perform by changing the variable simplifySteps (-1 to perform all steps).
  • To simplify the truth tree stepwise, click   simplify stepwise  . This will actually just increase the simplifySteps value in the declarations as described above.
  • By clicking on   truth table...  , you can generate the truth table which the BDD relies on.

Conversion
methods
For teachers Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!

Help for 'Huffman'

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. A Huffman code maps each symbol to encode onto a bit word such that the → Fano property is satisfied (no code word is prefix of another one) and the resulting code has minimal size when encoding a text with a specified probability distribution of symbols. The process of finding and using such a code proceeds by an algorithm developed by David A. Huffman while he was a Ph.D. student at MIT. Look → here for more information.

Usage in XWizard:

  • Write an arbitrary text as a base for the huffman tree.
  • Note that white spaces count as symbols, too.
  • The output depicts a Huffman tree. Running from its root to the leaves, the sequence of labels of the visited edges is the code of the encoded character (the upper-left corner of the according leaf label shows this character; its probability of occurrence in the corresponding text is given in the upper-right corner, the encoding in the bottom).
  • Note that the Huffman tree is usually not unique; particularly, labelling edges with 1 if they are drawn from right to left, and with 0 otherwise (as XWizard does it) is completely arbitrary. As long as each (non-leaf) father node has a 0 and a 1 edge leading to the according child node, all combinations are allowed.
  • Use the boolean variable classicView (click gray conversion button   format script   or   add declarations to script   to add declarations to a script) to switch between different views.

Conversion
methods
For teachers Create exercise from this script...
X

Create an exercise script from this script. Please enter parameters:

arg0: (String: Provide a short description or title for the exercise.)
arg1: (String: Enter a description for the exercise. You can use HTML.)
arg2: (String: Optional string to be entered by the user as a solution to this exercise.)
arg3: (String: Optional code string the user can earn by entering the correct solution.)
arg4: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by method name.)
arg5: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full script class name.)
arg6: (String: Optional → Regular expression (Java) to constrain displayed conversion methods - constrain by full target class name.)
arg7: (String: Optional explanation to be displayed with the solution.)
arg8: (boolean: Set this to true if the code of the exercise - not the complete script code - should be encrypted.)
arg9: (boolean: Set this to true if the complete script code should be encrypted.)

Debugging Stepwise script expansion...
X

Shows the stepwise expansion of the current script for debugging. (There is nothing to expand.) Please enter parameters:

arg0: (Boolean: Set to true to show in each step the currently available preprocessors.)

Example:

→ Draw!

Help for 'LogicCircuit'

Note that logic circuits are currently under construction and don't provide much functionality. Furthermore, their depiction can get pretty ugly for complex circuits - we are working on that. A logic circuit is given by a list of connections, each either
  • from a logic gate X to an input n of another logic gate Y as:
    X => Y.n;
  • or from an input I to an input n of a logic gate Y as:
    I => Y.n;
  • or from a logic gate X to an output O as:
    X => O;
Undefined elements I,O are treated as inputs or outputs, respectively. The remaining elements, i.e., logic gates, are defined in the declarations, e.g.:
components = A:NOT, B:XOR-nnin, C:XOR, D:AND, E:AND, F:OR;
More than two inputs are defined by a series of n and i (cf. B in the example) for 'normal' and 'inverted' inputs, respectively.


Collapsing/decollapsing rules: This script type is based on rules such as X => Y; Use button   format script   to collapse like this:

A => B;
A => C;
A => D;
to:
A => B | C | D;

or this:

A => D;
B => D;
C => D;
to:
A | B | C => D;

...or even this:

A => C;
A => D;
B => C;
B => D;
to:
A | B => C | D;

Collapsed rules provide the same information as decollapsed ones, i.e., they are equivalent in the above sense.

Help for 'Numbers'

LONG_TEST


XWizard documentation (see also → help pages):
XWizard 3_3.0 is the web version of → Very Fast PDF Generator. © Lukas König et al., 2007-2018 | → Contact
→ Empfohlen:

Neu und sehr gut!