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,499
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
  • 13.9k
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
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,735
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
  • 710
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
  • 13k
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.5k
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
  • 13.9k
2 votes

how to generate regular expression for the language where symbols have to maintain certain length?

The odd-odd language can be accepted by a four state finite state automaton. It stores for each of the symbols whether it has seen an even or odd number of that symbol. Thus we need two bits, one for ...
Hendrik Jan's user avatar
  • 30.5k
2 votes
Accepted

how to generate regular expression for the language where symbols have to maintain certain length?

I created a DFA recognizing the language and used the Brzozowski and McCluskey's algorithm (state elimination method) to obtain: $$(00\mid 11)^*(01\mid 10)\left(00\mid 11 \mid (01\mid 10)(00\mid 11)^*(...
Nathaniel's user avatar
  • 13.9k
2 votes
Accepted

Why can't we prove closure under concatenation using DFA?

My only copy of Sipser is the third edition. Here is the relevant quote, after Theorem 26, closure under concatenation of the regular languages. To prove this theorem, let’s try something along the ...
Hendrik Jan's user avatar
  • 30.5k
1 vote
Accepted

Does a language dictate the order of the word?

Yes, order matters. The fundamental operation used in the definition of language $L$ is "string concatenation", for which order is important. One question: if you were happy about ...
Stef's user avatar
  • 495
1 vote
Accepted

How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the question you've linked, we have $|xy| = |x| + |y| \leq p$ (property b) so $|y| \leq p$ since $|x| \geq 0$. Therefore $$|xy^2z| = |xyz| + |y| = 2^p + |y| \leq 2^p + p < 2^{p + 1}.$$
Knogger's user avatar
  • 710
1 vote

Is the $L'$ regular or not?

I think it's actually regular. Suppose $L$ is recognised by the DFA $A = (Q, \Sigma, \delta, q_0, F)$, define the NFA $A' = (Q, \Sigma, \delta', q_0, F)$ s.t. $$\delta'(q, a) = \{\delta(q, a)\} \cup \{...
Knogger's user avatar
  • 710
1 vote

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
  • 31

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