# Tag Info

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