New answers tagged regular-expressions
1
$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000 a b \n
0000003
This regex expression "$b*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since $b^*$ stands for the language $\{\epsilon, b, bb, \cdots\}$, where $\epsilon$ stands for the empty ...
0
No, there are no other possibilities as far as I can see.
The ambiguity comes from the production rule $expr \rightarrow expr - expr$. This rule allows you to derive the expression in two different ways:
Derive $1$ from the left $expr$ and the rest from the right $expr$
Derive $1-2$ from the left $expr$ and the rest from the right $expr$
Some ideas that ...
1
For a language that isn't regular, but satisfies the pumping lemma, take:
$$
L = \{a b^r c^r \colon r \ge 1\} \cup \{a^r b^s c^t \colon r \ne 1 \wedge s, t \ge 1\}
$$
Given $\sigma = a b^r c^r$, you can pump the starting $a$, the result is always in $L$.
Given a string that starts with no $a$, you can pump some starting $b$s; if it starts with 2 or more $a$...
1
Here is the version of Arden's theorem on Wikipedia:
One solution of the language equation $R = Q+RP$ is $R = QP^*$.
If $\epsilon \notin P$, then this is the only solution.
When $\epsilon \in P$, there are more solutions. In fact, we can prove the following result:
The solutions of the language equation $R = Q+RP$, where $\epsilon \in P$, are $R=...
3
Yes, $L_>=\{0^i1^j: i > j > 0\} $ is a non-regular language.
However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $p$ is a pumping length for $L_>$. Consider $w=0^{p+1}1^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$....
1
The rule for the $\sigma\in \Sigma$ must be applied each time a letter appears in the regular expression, not only once per letter : you must build a different automata each time the letter appears. If you see it as some kind of digital circuit, you do not want to use the circuit that recognizes $a$ in $ab$ for the circuit that recognizes $a$ in $a + \...
Top 50 recent answers are included
