# 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: ...
177 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 ...
15 views

23 views

### regular expressions, notation w|w and w|?

I'm trying to give regular expressions for the following languages {a, b} What does w| and w|w mean? For the first question, I have (b(a+b))*, but I'm lost on the second.
116 views

### Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
124 views

62 views

### Derivation: Discerning difference between arithmetic expression with parenthesis versus without using abstract syntax trees

I am trying to illustrate the expression: ( 3 * 4 + 5 * 6 + 7 ) using an abstract syntax tree. I have already illustrated the expression: ( 3 * (4 + 5) * (6 + 7) ). Could someone please illustrate ...
34 views

### One-to-one correspondance between regular sets

I have problem with one-to-one correspondance "One-to-one correspondence with the set (B) of all tags possible being represented with their binary representation (i.e. 0, 01, 00, 010101, 11000, 01010,...
60 views

### Does there exist a regular expression for a series of points?

If I was looking for a certain "shape" or "pattern" in a simple line chart is there a way to describe the series of points that would make up this "shape"? Example: If I had a line chart and I was ...
30 views

### productions with identical right hand sides for different nonterminals

Can a regular grammar contain two productions with identical right hand sides? I know in context free grammars shift reduce parsers issue reduce reduce conflicts when smth like this happens. What are ...
48 views

### How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with $a$ and ending with $b$ is written as $a(a+b)^*b$ Can some one tell me how to write this
### Regular expression of: $\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}$.
Given $\Sigma = \{ 0,1,2 \}$, write a regular expression for $$\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}\;.$$ I know how to do a regular expression for a language that does ...
I have this language L that contains only one string: $a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3}a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3} ....a_{n}...a_{n}$ written more concisely \$(..(a_{1}^{2}a_{2})^{2}a_{3}^{...