In the expressions, the dot operator is omitted and some parentheses are omitted
ID: 3743052 • Letter: I
Question
In the expressions, the dot operator is omitted and some parentheses are omitted, in which case the Kleene star operator (*) has the highest precedence, followed by the dot operator (.), followed by the or operator (|). Let getToken() be a function that returns the next token in the input. If we call it repeatedly it will return one token after another. When all the input is consumed, getToken() returns EOF (end of file). Assume that longest prefix-matching rule is used by getToken() and ties are broken in favor of the regular expression listed first.
Problem 1. Consider the following regular expressions Re-1| 2| 3 R1 1 | 2 1418 R2 -(a | b) (a* | b*) (a | b)Explanation / Answer
1 ) Input String can be any combination of 1,2 and 3 , but the length should be two
Example 12 , 13, 11, 22, 33, and other combinations
2) R1 can produce 1 or 2 or 4 or 8
So input String can be any combination from above of length 2
example: 14
3) R2 can produce a or b
a* signifies 0 or more number of 'a'
Example: aa, ab, ba.bb
4) R3 can also be written as (a*+b*) (1+2+4+8)* (ab)*
This Expression can be considered into as parts
first is (a*+b*)
second is (1+2+4+8)*
third is (ab)*
CONSIDERING SECOND AND THIRD PART OF REGULAR EXPRESSION AS NULL
If in first part, a* produces null and b* produces bb then this can be considered as input
OR
If a* produces aa then b* should produce null, as we gettoken() is called twice. Therefore, aa can be considered as input
OR
a* produces a and b* produces b so we get ab as the input
CONSIDERING FIRST AND THIRD PART AS NULL, THAT IS BOTH PARTS ARE PRODUCING NULL
Second part can produces any combination of 1,2,4,8 twice
example: 12,14,18,11,and so on.
CONSIDERING FIRST AND SECOND PART AS NULL
Third part is (ab)*
that means this can only give ab as input.
Note: there can also be cases in which only one part is null.
CONSIDERING THIRD PART AS NULL
that means input string should have first letter from first part of regular expression and second letter from second part of regular expression.
Example: a1, a2, a4, a8, b1, b2, b4, b8
5) As the Regular Expression contains ab as prefix
so if gettoken() is to be called twice then, this regular Expression can produce ab as input.
6) This regular Expression cannot contain string of length two as minimum string length it can produce is aaa
which doesnot meet our requirements