Recall the balanced$-$parenthesis language Paren from Problems $4\mathrm{.}7\mathrm{.}6$ and $4\mathrm{.}7\mathrm{.}7,$ and Section

$14\mathrm{.}2.$ Let L$3$ be the subset of the Paren consisting of all strings that never have a prefix

whose excess of L$$s over R$$s is greater than $3.$ Build a DFA for this language, and apply

state elimination to get a regular expression for it$.$

Note. P $4\mathrm{.}7\mathrm{.}6$ defines Paren as follows:

$($a$)$ is in Paren.

$($b$)$ If u is in Paren,then so is LuR.

$($c$)$ If u and v are in Paren, then so is uv$.$

$($d$)$ No other strings are in Paren.

P $4\mathrm{.}7\mathrm{.}7$ States that Paren is equivalently the language characterized by the following two

properties. A string w in $\{$L$,$ R$\}$ is in Paren if and only if

$(1)$ The number of L$$s and R$$s in the string is equal

$2)$ In any prefix of the string, the number of L$$s is at least as great as the number of R$$s$.$

You should use the minimal DFA for this language, which has five states. Then you$$re

asked to create a regular expression from this DFA, using the state elimination algorithm

from lecture.