New answers tagged

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