11 votes
Accepted

Is the language given by the regex (ab)* star-free?

No. $L=(ab)^*$ is star-free. A word is in $L$ iff It starts with $a$ (or is empty) It ends with $b$ (or is empty) It does not contain any consecutive $a$'s It does not contain any consecutive $b$'s ...
D.W.'s user avatar
  • 159k
8 votes

Notation in NFA, DFA diagrams and language

You need to distinguish between three kinds of operations: Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer ...
reinierpost's user avatar
  • 5,539
8 votes
Accepted

How to show L is non-regular without pumping lemma?

Well, you can't show that it is not regular, because it is regular. Indeed, $L = (ab)^*\setminus \{(ab)^6\}$, and $(ab)^*$ is regular (concatenation + kleene star), and $\{(ab)^6\}$ is regular (...
Nathaniel's user avatar
  • 15.6k
6 votes

Proof that a union of two non-regular languages may be regular

Let $L_2 = A^* \setminus (L_1\cup \{\varepsilon\})$. Then $L_1 \cup L_2 = A^*\setminus \{\varepsilon\}$ which is regular and not equal to $A^*$.
Nathaniel's user avatar
  • 15.6k
6 votes
Accepted

What does empty string ε actually mean?

Regular expressions represent sets of strings, so $\varepsilon$ in that expression represents the set that contain only the 0 length string, $\{\varepsilon\} $. This of course is not the same as the ...
Russel's user avatar
  • 2,745
6 votes

Notation in NFA, DFA diagrams and language

Consider a finite nonempty alphabet $\Sigma$. The set $\Sigma^* = \bigcup\limits_{n\geq 0 } \Sigma^n$ is the set of finite words over $\Sigma$, indeed, for all $n\geq 0$, we define $\Sigma^n$ as the ...
Bader Abu Radi's user avatar
5 votes

Prove or disprove that two regular languages are equivalent

It's hard to give hints without solving the problem for you. Some general hints: When working with regular expressions, the $^+$ sign ("one or more") is a useful shorthand: $X^+ = XX^* = X^*...
reinierpost's user avatar
  • 5,539
5 votes

Proof that a union of two non-regular languages may be regular

Nowhere does the question state that the intersection of $L1$ and $L2$ must be empty. Also for L1 to contain the empty string it must be that $m = n =0$ in the description, however $m,n >0$, ...
ratchet freak's user avatar
5 votes

Notation in NFA, DFA diagrams and language

For a (usually finite) set $A$ the star denotes the free monoid on $A$ where $$A^* = \{a_1a_2...a_k : k \geq 0 \land \forall i. a_i \in A\}$$ is the set of all finite sequences or strings of elements ...
Knogger's user avatar
  • 1,032
4 votes

Proving that the scramble of a regular language is context-free

We can prove this without using Parikh's theorem. Assume that a language $L$ over the two-letter alphabet $\{0,1\}$ is given by a finite-state machine. For the language $\mathrm{SCRAMBLE}(L)$ we ...
Mati's user avatar
  • 63
4 votes

Why can't I prove that the regular language is closed under concatenation by this way?

Actually, that works if you add $\varepsilon$-transitions between final states of $M_1$ and the initial state of $M_2$. His argument of "maybe the cut of $w$ was wrong and you should have waited ...
Nathaniel's user avatar
  • 15.6k
4 votes
Accepted

How to handle odd word

I have no idea what exactly you're asking, but if you consider $w = a^{2p}$ to be a valid answer for even-sized words, I assume $w = a^{2p+1}$ would be fine for odd words.
orlp's user avatar
  • 13.4k
4 votes
Accepted

regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

The only systematic ways to find regular expression I know of are using automata. As D.W. mentionned in his comment, I am not sure why you are rejecting this method. A non-systematic approach for this ...
Nathaniel's user avatar
  • 15.6k
4 votes

A more concise Finite Automata for 10 substring?

Your automaton (automata is the plural word) is wrong: as @Knogger stated, there is no initial state finite automata (unless generalized) can only have one-letter transitions, so transitions $01$ are ...
Nathaniel's user avatar
  • 15.6k
3 votes

Is the set of all strings over $\Sigma$ countably infinite or not?

$\lambda$, $a$, $b$, $aa$, $ab$, $ba$, $bb$, $aaa$, $aab$, $aba$, $abb$, $baa$, $bab$, $bba$, $bbb$, $aaaa$, $\dots$,
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

Does my finite state automaton accept a string iff it contains the given string as a substring?

Remarks on your FSA Your specification of the FSA is not finished. The transitions from states other than $q_n$ where the symbol read is not in $S$ are not defined. ambiguous. What happens if $s_1=...
John L.'s user avatar
  • 39k
3 votes
Accepted

Proving the set $R$ is finite

There exists an infinite sequence of strings, such that no string is a substring of another. For example $a b^* a$. If one considers the subsequence ordering instead of the substring ordering, then ...
Hendrik Jan's user avatar
  • 30.6k
3 votes

Proof that a union of two non-regular languages may be regular

If you don't want $L_2$ to be the complement of $L_1$ (as then $L_3$ would the set of all words), then you can simply choose $L_2$ to be $\overline{L_1}\setminus L$, where $L$ is a nonempty finite ...
Bader Abu Radi's user avatar
3 votes
Accepted

How to handle multiple exponents (Pumping-Lemma)

There is actually a more generalized version of the pumping lemma, where you can pump a substring anywhere in the word. The proof is almost the same: in a computation of a word $w$ in a DFA, if there ...
Nathaniel's user avatar
  • 15.6k
3 votes

How to handle multiple exponents (Pumping-Lemma)

There is a solution to your pumping problem using the classical formulation of the Pumping Lemma, writing $w=xyz$ and considering $|xy| \le p$ and $xy^iz$ for $i\ge 0$. The trick is pumping down... ...
Hendrik Jan's user avatar
  • 30.6k
3 votes

NFA for a regular expression without $\epsilon$-transitions

You can convert the regular expression into an automaton using the Glushkov's construction. The resulting automaton is non-deterministic and does not contain any $\varepsilon$-transition. Its number ...
Nathaniel's user avatar
  • 15.6k
2 votes
Accepted

Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$

To show that a language $L$ is not regular you need to argue that the pumping lemma does not hold. That is, you want to show that for every $p$, there exists some word $w$ such that, for every ...
Steven's user avatar
  • 29.5k
2 votes

Rational subsets of a monoid

Yes, it's a lifting of the monoid product $$x, y ∈ M ↦ xy ∈ M$$ onto a product $$A, B ∈ 𝔓M ↦ AB ∈ 𝔓M,$$ that makes the power-set $𝔓M$ of $M$ into a monoid, and $M$, itself, a sub-monoid of $𝔓M$ ...
NinjaDarth's user avatar
2 votes
Accepted

Counting States in the trim automaton for $L\circ L'$

For clarity, automata are assumed deterministic and possibly incomplete in the question and this answer. A trim automaton is incomplete unless it is empty or it accepts all strings. As your argument ...
John L.'s user avatar
  • 39k
2 votes

Can you enumerate the set of all words over a finite alphabet?

I think that the original poster wanted to point out that lexicographic order does not work for the purpose of enumerating all words. 1 11 111 1111 ... and you never reach 2 (and you miss 0). Of ...
Pierre ALBARÈDE's user avatar
2 votes

Languages having only one Myhill–Nerode equivalence class

Let $L \subseteq \{ a, b\}^*$ be a language with one Myhill-Nerode equivalence class. You can show that $L$ must be trivial, that is $L\in \{\emptyset, \{a, b\}^*\}$, either by using the Myhill-Nerode ...
Bader Abu Radi's user avatar
2 votes

Is the set of all DFAs countable?

There are several ways to prove this. Here is a formal one: You can encode the set of DFAs over $\Sigma$ as words over the constant alphabet $\Sigma' = \{0, 1, \#\}$. This can be done as follows. Let $...
Bader Abu Radi's user avatar
2 votes

How to prove that $L=\{0^m1^n\;|\; \mathbf{gcd}(m,n)=1\}$ is not regular

This sounds like homework so I will just give a high level idea. The idea behind the pumping lemma is that regular languages are so structured that any long enough word in the language has a sub-word ...
Bernardo Subercaseaux's user avatar
2 votes

Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?

If you think the language is regular, there is no point using the pumping lemma. It is used to prove that some languages are NOT regular. The sentence "$\{0,1\}^*$ can represent the NFA for the ...
Nathaniel's user avatar
  • 15.6k

Only top scored, non community-wiki answers of a minimum length are eligible