# Tagged Questions

Regular expressions or Regex is a search pattern for strings defined by a sequence of characters.

38 views

### Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] [s,a,x,a,...
136 views

### Build regular expression from language

I have the following language: L = {w $\in$ {a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the ...
168 views

### Regular expressions represents the sets provided

While I am studying formal languages, I see these questions.What are the answers for them? a) The set of strings over {a, b, c} that begin with a, contain exactly two b’s, and end with cc. b) The ...
28 views

### A newbie need some help in proof building. How to prove that any regular expression admits a disjunctive normal form?

Prove that any regular expression admits a Disjunctive Normal Form, i.e.: R = R1 U R2 U … Rn , where neither Ri contains a union. I would like some help with this question. If you could push me into ...
15 views

### Regular expression building: Comment delimited strings

I'm attempting to build a regular expression that will accept only strings of the form: ...
179 views

### $L_1 =(a^nb^n)$ and $L_2 =(a^nb^{2n})$. Is $L_1 \cup L_2$ DCFL?

I think that since $a^nb^n$ is not regular (applied pumping lemma), so is $L_2$. Therefore, $L_1 \cup L_2$ is not cfL. Is that correct?
88 views

### Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^*$: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
158 views

### Complement of a Set of Strings in a Language

Suppose $B= \{ 0^n1^m2^{n-m}:\, n\ge m\ge 0 \}$ Is the complement $\overline B = \{ 0^n1^m:\, 0\le n\lt m\}$? Or is it the universe of all possible strings (including all strings with symbols ...
55 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 ...
Suppose there is a simple NFA, with 3 states (p,r,q) where p is the start and r is the final. Such that $\delta$ = (p,a,q), (p,b,q), (p,a,r), (p,b,r), (q,a,p), (q,b,p), (q,a,r), (q,b,r), (...