Write regular expressions

Assignment Help Theory of Computation

Reference no: EM13801462

Question 1- Write regular expressions to capture the following.

(a) Strings in C. These are delimited by double quotes ("), and may not contain newline characters. They may contain double-quote or backslash characters if and only if those characters are "escaped" by a preceding backslash. You may find it helpful to introduce shorthand notation to represent any character that is not a member of a small specified set.

(b) Comments in Pascal. These are delimited by (* and *) or by { and }.

Question 2- Show(as"circles-and-arrows"diagrams)the finite automata for question 1.

Question 3- (a) Show the NFA that results from applying the construction of Figure to the regular expression letter ( letter | digit )*.

2481_figure 2.7.png

(b) Apply the transformation illustrated by Example 2.14 to create an equivalent DFA.

Question 4- (a) Describe in English the language defined by the regular expression a* (b a* b a* )* . Your description should be a high-level characterization-one that would still make sense if we were using a different regular expression for the same language.

(b) Write an unambiguous context-free grammar that generates the same language.

(c) Using your grammar from part (b), give a canonical (rightmost) derivation of the string baabaaabb.

Question 5- Give an example of a grammar that captures right associativity for an exponentiation operator (e.g., ** in Fortran).

Question 6- Consider the following grammar:

G → S $$

S → A M

M → S |ε

A → a E | b A A

E → a B | b A|ε

B → b E | a B B

(a) Describe in English the language that the grammar generates.

(b) Show a parse tree for the string abaa.

(c) Is the grammar LL(1)? If so, show the parse table; if not, identify a prediction conflict.

Question 7-Consider the following CFG for floating-point constants, without exponential notation. (Note that this exercise is somewhat artificial: the language in question is regular, and would be handled by the scanner of a typical compiler.)

C → digits . digits

digits → digit more_digits

more_digits → digits|ε

digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Augment this grammar with attribute rules that will accumulate the value of the constant into a val attribute of the root of the parse tree. Your answer should be S-attributed.

Reference no: EM13801462

Questions Cloud

Problems based on the use statistics for inference : Write a 90% confidence interval for the mean daily income this parking garage will generate.

Describe some of the main services of public organization : Create, describe, and explain the type of fictional public organization. Describe some of the main services, products, and activities the organization provides to the public.

What would someone who is a terrorist do : What would someone who is a terrorist do? What would a terrorist refrain from doing? Is there anything you can think of that people who are terrorists would HAVE to do? (If they didn't they wouldn't be terrorists).

Describe how terrorist groups use social media : Describe how terrorist groups use social media. Analyze how future technology trends may help terrorist groups support their agendas.

Write regular expressions : Write regular expressions to capture the following-Strings in C. These are delimited by double quotes ("), and may not contain newline characters. They may contain double-quote or backslash characters if and only if those characters are "escaped" b..

Interval estimate of the population slope issues : At the 0.05 level of significance, is there a significant linear relationship between two variables?

Examine the overall roles of the non-state participants : From the second e-Activity, examine the overall roles of the Non-State participants within a current event that requires a foreign policy on terrorism to be developed. Provide a rationale for your response.

General discussion of online course design and development : General Discussion of Online Course Design and Development

Advances in technology-responsibilities of global : Examine the relationship between advances in technology and the responsibilities of global citizenship. Describe how technology has changed the way in which people pursue knowledge and how they address social concerns.

User Account

All Pages