# Tagged Questions

37 views

### Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
36 views

### Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
30 views

### Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
76 views

### Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
216 views

### How to prove that the following language is not regular?

This is the following problem that I've been having difficulty on: For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the ...
This is a question I've been stuck on recently: Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and \$L(S) ...