编程代写｜Practice Final Exam: Formal Language Theory

本次美国作业是一个编程语言相关的编程代写assignment

Question 1

Consider this regular expression:

Which of the following regular expressions is/are equivalent to it?

0(1*|1)
1|0(1*)
(1|0)1*
(01)*|1
0|1*|1

Question 2

Provide the DFA (deterministic finite automaton) for the regular
expression (same as in question #1):

You do not have to use the method of converting to an NFA first,though of course you may.

Question 3

Consider the following deterministic finite automaton:

Which of the following strings is/are not accepted by this automaton?

b10110100111
a
0010
empty string
bb101

Question 4

Why aren’t regular expressions used in the parsing stage of language translation to determine that tokens follow a grammatically correct pattern?

Because parsing is concerned with type and scope analysis, and regular expressions cannot express these context-sensitive issues. Because regular expressions cannot express balanced characters, such as balanced parentheses.

Because the implementations of regular expressions (finite automata) are less efficient than the implementations of context free grammars.

Because regular expressions cannot express languages that are infinitely large.