Write a regular expression for unsigned binary integer

Assignment Help Theory of Computation

Reference no: EM13702290

Part 1: Define a language for unsigned binary integer numbers. An unsigned binary integer number consists of any number of digits (0 or 1), but contains no leading zeros. For example, 0, 1, 100, 101, 10 are all acceptable integers, but 00, 01, 0001, 0101 are not.

Q: Write a regular expression for unsigned binary integer numbers described above.

Part 2: Transform the regular expression to an NFA.

Part 3: a - Transform the NFA to a DFA using the algorithm.

b - Transform the DFA to a minimum state DFA using the algorithm.

Part 4: Transform the NFA to regular grammar.

Part 5: Write a context-free grammar for arithmetic expressions consisting of non-negative binary integer numbers defined in Activity 1 and four operators, + (addition), - (subtraction), * (multiplication), and / (division).

No precedence needs to be considered in the grammar. In addition, no parentheses will be used in expressions.

For case, (10 + 1) * 101 is not acceptable. The regular grammar you have obtained in part 1 should be included as part of your solution.

Part 6: Transform the context-free grammar obtained in Part 5 to a pushdown automaton.

Part 7: Write parsers for arithmetic expressions. Transform your grammar into a LL(1) grammar.

You may need to do a left-factoring of common prefix of productions, and/or to remove any left-recursive productions in the grammar for arithmetic expressions. Then prepare a recursive-descent parser for the context-free grammar for arithmetic expressions.

Part 8: Use the LL(1) grammar obtained in Activity 7 and design the parse table for top-down parsing. Include the computation of all first sets and follow sets in your answer.

Part 9: Design a Turing machine that accept expressions defined in Part 5.

Suppose the tape head is initially at the left end of the input string. If the input string is acceptable, the tape head must be at the right end of the output string. There are no blank cells in the input string.

You need to prepare a regular expression for unsigned binary integer numbers explained in the above question.

Reference no: EM13702290

Questions Cloud

Intensity for isoamyl acetate infrared spectral analysis : Question- Indicate the function groups, wave number and peak intensity for isoamyl acetate infrared spectral analysis

Naf in order to initiate a precipitate of calcium fluoride : Question- Calculate the minimum concentration of Ca2+ that must be added to 0.10 M NaF in order to initiate a precipitate of calcium fluoride.

What is the largest x such that the protocol performs x-bit : What is the largest x such that the protocol performs x-bit correction and what algorithm would you use to perform this correction? Give me the pseudo-code (or a sensible explanation)

Can discoveries continue to keep up with depletion : In working out your responses to the Discussion Question, you should choose examples from your own experience or find appropriate cases on the Web that you can discuss. Credit will be given for references you make to relevant examples from real co..

Write a regular expression for unsigned binary integer : Write a regular expression for unsigned binary integer numbers described - Define a language for unsigned binary integer numbers.

Calculate the molar solubility of iron(ii) sulfide : Question- The solubility product, Ksp, for iron(II) sulfide is 6.0 x 10^-19. Calculate the molar solubility of iron(II) sulfide

What is the ph at the equivalence point in the titration : Question- What is the pH at the equivalence point in the titration of 100 mL of 0.25 M HCN (Ka = 4.9 x 10^-10) with 0.25 M NaOH

Properties of a generator polynomial : For each of the "desirable" properties of a generator polynomial G discussed in class, show whether G above satisfies each of these properties or not.

Calculate the minimum concentration of ca2+ : Question- Calculate the minimum concentration of Ca2+ that must be added to 0.10 M NaF in order to initiate a precipitate of calcium fluoride.

User Account

All Pages