Home /
Expert Answers /
Computer Science /
problem-3-15-marks-give-a-recursive-procedure-that-decides-given-r-if-l-r-is-inf-pa696
(Solved): Problem 3. (15 marks) Give a recursive procedure that decides, given \( R \), if \( L(R) \) is inf ...
Problem 3. (15 marks) Give a recursive procedure that decides, given \( R \), if \( L(R) \) is infinite. Explain why each case is correct. 1 COMP2022/2922Assignment 1 (8o marks) - Regular Expressions S2 2022 Hint: You may find it helpful to design a procedure that obtains and uses some additional information about the subexpressions beyond whether their languages are infinite. Note: Your solution should be a recursive procedure operating directly on \( R \). For example, using the RE to NFA conversion (from week 3) is not allowed. At least 5 marks will be awarded for the base cases and union case.
Expert Answer
Solution Let R be a regular expression over (?,?). We will use the following procedure to decide if L(R) is infinite: isInfinite(R): if R is a ?-transition then return true else if R is a character then return false else if R is a concatenation then