What does the "?" mean in generated language grammar?

48 Views Asked by At

I know $a^*$ means that a string could be composed of zero to infinite $a$'s, and $a^+$ means one or more $a$'s. But the professor posted this question...

Given the regular expression $b?a(a|b)ab?$ Do the strings "aaaba" , "baabb" belong to the language defined by this regular expression?

I don't need the answer to the problem, what I need to know is what does the $?$ symbol mean???

1

There are 1 best solutions below

0
On BEST ANSWER

$X?$ probably means that $X$ may or may not appear at that point. Formally, you can consider it an abbreviation for $$(X|\epsilon)$$ where $\epsilon$ means the empty string.