Hi, This part is about regular expressions (REs) and finite-state automata (FSAs). Notation: in the REs below, the Kleene star has higher precedence than sequencing; and sequencing has higher precedence than +. E.g. 10∗1 + 11∗1 = (1(0∗)1) + (1(1∗)1). Consider the regular expression r: (01 + 11)∗10 (1∗ + 0∗) 1.1) Which of the following words (ε is the empty word) belong to the language defined by r? Options: ε, 101, 001101, 111011, 111010 1.2) For each of your answers in Question 1.1, give a brief explanation. For example, you can explain how the regular expression will accept (i.e. match) the words that belong to its language, and how it will not accept those that do not belong in it. 1.3) Give, as a transition graph, an FSA (possibly with ε-transitions) recognising the same language as r. Note: You should not use transitions with composite labels, e.g. of the form q1 →42→ q2.
Hi, This part is about regular expressions (REs) and finite-state automata (FSAs).
Notation: in the REs below, the Kleene star has higher precedence than sequencing; and
sequencing has higher precedence than +. E.g. 10∗1 + 11∗1 = (1(0∗)1) + (1(1∗)1).
Consider the regular expression r: (01 + 11)∗10 (1∗ + 0∗)
1.1) Which of the following words (ε is the empty word) belong to the language defined
by r?
Options: ε, 101, 001101, 111011, 111010
1.2) For each of your answers in Question 1.1, give a brief explanation. For example, you can explain
how the regular expression will accept (i.e. match) the words that belong to its language, and
how it will not accept those that do not belong in it.
1.3) Give, as a transition graph, an FSA (possibly with ε-transitions) recognising the same language as r.
Note: You should not use transitions with composite labels, e.g. of the form q1 →42→ q2.
Thanks for the help :)
Step by step
Solved in 4 steps with 1 images
