On considère l’alphabet A = {a, b} et on donne la définition inductive d’un regex R comme
- R est une lettre de l’alphabet A
- R est (P.S) où P et S sont deux regex
- R est (P|S) où P et S sont deux regex
- R est (P*) où P est un regex
- R est (P+) où P est un regex
Toute expression régulière sera nécessairement parenthésée. On définit alors l’ensemble L(R) des mots reconnus par un regex R :
- R est “(x)” où x est dans l’alphabet A; L(R) = {x}
- R est (P.S); L(R) = {ps, p ∈ L(P) ∧ s ∈ L(S)}
- R est (P|S); L(R) = L(P) ∪ L(S)
- R est (P*); L(R) = La concaténation de 0 ou plusieurs mots reconnus par P
- R est (P+); L(R) = La concaténation d’un ou plusieurs mots reconnus par P
Input
2N lignes de regex R et de nombres n.
- 150 ≤ N ≤ 300
- 2 ≤ n ≤ 16
- Profondeur p(R) du regex : 2 ≤ p(R) ≤ 5
Output
Il est demandé d’afficher N lignes, contenant chacune le nombre de mots de longeurs au plus n dans l’alphabet A* reconnus par le regex.
Exemples
Input :
(a.((((b+)|(b|b))|b)*))
16
(((((b+).(a.a))+)|a)*)
15
(b*)
14
Output :
16
4410
15