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

learn more… | top users | synonyms

0
votes
2answers
325 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
0
votes
1answer
27 views

Write each of the following languages from the alphabet is ∑ = {0, 1} as a regular expression:? [closed]

a) All even length strings that end with 0 b) All odd length strings with a 0 in the middle. c)Strings that are divisible to 3 when interpreted as a positive binary number(for ex.,0011,001001,1100,...
0
votes
1answer
15 views

Regular expression that begins and ends with digit

I'm trying to write a regular expression that defines all words written in lower case characters and digits that begin with a digit, end with a digit and contain total of 4 digits. My idea is : $[0-...
1
vote
3answers
66 views
0
votes
0answers
20 views

Regular expression that defnes the set of all words

I'm trying to write a regular expression that defines the set of all words written in lower case characters and digits that contain a binary number. My idea: $(\varepsilon |[a-z]^{*})(\varepsilon |(...
0
votes
1answer
572 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
1
vote
2answers
29 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
-1
votes
2answers
53 views
1
vote
1answer
27 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
0
votes
1answer
10 views

Order of expressions in regular expressions?

Does the order of expressions in regular expressions matter? For example: Can I write for example $(a^*)b$ as: $(a^*)b$ = $b(a^*)$ ? What about the following? $a^mb^n = b^na^m$ $a^nb^n=b^na^n$ $...
0
votes
0answers
21 views

Checking if regular expressions are equivalent

Is there a quick script/tool to check if two regular expressions are equal? For example: I want to know if 0*(01 + 11) is equal to ...
0
votes
1answer
36 views

Deterministic finite automaton parity bit question

for a university assignment ive been tasked with creating a DFA that accepts the regular language (00010 + 1101 + 1010)* and must contain a parity bit at the end to make sure there is an even amount ...
1
vote
1answer
70 views

Is the language of complex numbers regular?

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ ...
0
votes
1answer
20 views

If $L_1.L_2$ is regular, and $L_1$ is regular, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. Now, Is this true? Assume that $L=L_1.L_2$ is a regular language. Also ...
1
vote
1answer
87 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 ...
0
votes
3answers
46 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: $$ ( a + b )^* a ( a + b )^* b( a + b )^* = (a + b)^* ab(a + b)^* $$ I can "see" why they are equal to ...
0
votes
2answers
41 views

How to convert DFA into RE?

So I am trying to convert this DFA into an Regular Expression. I got an answer but I am not 100% is correct I feel like it is too long. From my understanding, I just need to find the transitions into ...
0
votes
2answers
143 views

Converting NFA to DFA and then to regular expression.

Convert the NFA into a DFA and then into a regular expression defining the language accepted by this NFA. NFA So far I have converted to a DFA (I hope) but do not know how I can convert to a ...
1
vote
3answers
47 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
5
votes
0answers
9 views

Solving the equation X = AX + B of languages for X [duplicate]

I'm currently working on the following problem for my computer theory class. It goes as follows: Let $A$ and $B$ be regular expressions. Show then that $A^* B$ is the solution of $X = AX + B$. ...
0
votes
1answer
19 views

A regular expression for the language $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$

A language like $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$ is given. The first question : Is this language regular? The second question : If $L$ is regular, How can we write a regular ...
0
votes
2answers
26 views

Simplify $\sqrt{x(x^{2n+1})} \over \sqrt[3]{x^{3n}}$

I need to simplify $$\sqrt{x(x^{2n+1})} \over \sqrt[3]{x^{3n}}$$ I think I can do it, if I knew how to do: $$x(x^{2n+1})$$ wouldn't it be $$x^{2n +2}$$
0
votes
1answer
25 views

A regular expression for the language $L=\{w:(n_a(w)-n_b(w))mod3=1\}$

Assume a language like $L=\{w:(n_a(w)-n_b(w))mod3=1\}$ is given. How can i find a regular expression for this language using a systematic process? Note : I can easily draw a DFA accepting this ...
0
votes
2answers
35 views

non-deterministic automaton and regular expression

I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet $\{a,b,c\}$ that accept all and only those strings ...
0
votes
1answer
21 views

regular expressions Sequences [closed]

Can any one help with this ? Not sure how to do it For an alphabet: $A = \{a, b, c, d\}$ For each of the words $abc$, $cbc$, $ac$, $cca$, and $bbba$, determine whether the word matches each of the ...
1
vote
1answer
167 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 ...
-1
votes
1answer
303 views

Show that $\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$ is not regular

How can I show this?I don't know how to start. Show that the set given below is not regular. $$\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$$
1
vote
1answer
54 views

Regular expression of the set of strings of even length

I should try to write a regular expression of the set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. If string has even length, and if we have one $k$; there should be (odd ...
2
votes
1answer
31 views

Determine string is even length with regular expression

There is a set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. And I try to write its regular expression. I think it can be in that format: ...
1
vote
1answer
45 views

Construct a regular expression for a given language

I'm currently working on some exercises to get used to create regular expressions from given languages and i'm stuck with a fairly simple exercise. So could you please tell me how to construct it step ...
2
votes
4answers
76 views

Why are complex numbers allowed to be combine like this?

The problem This expression is meant to be simplified. Why does it make sense to write $$\frac{1}{1-6i} - \frac{1}{1+6i} = \frac{1+6i−(1−6i)}{(1−6i)(1+6i)} \quad ?$$ How can the rules followed here ...
0
votes
0answers
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
3
votes
1answer
23 views

Language of binary multiplications relation.

Given $\Sigma = \lbrace 0, 1 \rbrace$ and $L \subseteq (\Sigma \times \Sigma \times \Sigma)^*$. Let $first(w), second(w), third(w)$ be word from $(\Sigma \times \Sigma \times \Sigma)^*$ limited to ...
1
vote
4answers
49 views

Regular expressions: Show that A*B is the solution of X = AX + B

I'm currently working on the following problem for my computer theory class. It goes as follows: Let $A$ and $B$ be regular expressions. Show then that $A^*B$ is the solution of $X = AX + B$ ...
4
votes
3answers
117 views

Number of sequences that contain a given “run”

Consider sequences of numbers 0, 1, 2 with length n. There are $3^n$ such sequences. I want to know how many sequences there are that contain a k-run of 1's followed by 2. As a regular expression: ...
1
vote
1answer
27 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 ...
1
vote
1answer
33 views

How to prove $\forall x,y\in\mathbb{R} : x^3+x^2y=y^2+xy \Leftrightarrow y=x^2\lor y=-x?$

Let $x,y\in\mathbb{R}$ Assume $x^3+x^2y=y^2+xy$ Then $x^2(x+y)=y(x+y)$ Then either $(x+y)=0$ or $(x+y)\ne0$ Assume $x+y=0$ Then $y=-x$ Assume $(x+y)\ne0$ Then $y=x^2$ Then $x^3+x^2y=y^2+xy \...
1
vote
2answers
31 views

Proving a Regular Expression

$L$ is a language from the alphabet $\Sigma = \{a,b \}$. Define $C(L)$ as another language. This language produces a $w$ as an element of $\{a,b\}^*$ with the property that there exists a $v \in L$ ...
1
vote
1answer
68 views

Regular expression for strings with even number of 1's and number of 0's divisible by 5

I am able to write a DFA for this language but don't see any good way to convert this into a regular expression. This is the DFA I came up with:
1
vote
0answers
60 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be invalid....
0
votes
1answer
29 views

Prove regular expression with induction

I need help proving the following regular expression via induction. I have the base case (easy of course) but I'm having a difficult time determining the inductive case. A regular expression over ...
0
votes
1answer
19 views

power + operator for binary

What is the specific definition for power $+$ operator in automata theory? For example, when $x$ is a binary what does it mean that $x = 0^+$. Does it mean that x is a string with at least one $0$?
1
vote
1answer
24 views
1
vote
1answer
31 views

Finite Automata for regular expression

I am trying to construct finite automata for this regular expression: Every block consisting of 5 characters need to contain at least two zeros. The regular expression would look sth like this: (00(1|...
0
votes
1answer
50 views

Prove that if $L$ is regular, then $f(L)$ is regular too

Prove that if $L$ is regular, then $f(L)$ is regular too. $\Sigma_1$ and $\Sigma_2$ are two arbitrary alphabets, $f$ is a function that maps every symbol of $\Sigma_1$ to an element in $\Sigma_2$, i....
0
votes
0answers
42 views

Regular and context free language

Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$. It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that $...
0
votes
4answers
53 views

If $A^{2x}=4$ what is ${A^{3x}-A^{-3x}\over A^x - A^{-x}}$

If $A^{2x}=4$ and $A > 0$, what is the numerical value of $${A^{3x}-A^{-3x}\over A^x - A^{-x}}$$ Could anyone find the solution and answer? Thanks
1
vote
1answer
61 views

Language with middle third removed

Originating from Sipser's book: Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed. The solution I came across makes the ...
0
votes
1answer
102 views

Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

My question originates from Sipser's book. Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define: NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A} NOEXTEND(A) ...
3
votes
2answers
1k views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...