The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
29 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
0
votes
0answers
21 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 ...
2
votes
1answer
33 views

Equivalence of regular expression

Let $ A = \{a,b\}$ be an alphabet. Please hint me with show, that this regexes are equivalent. That means, we should show that: $L(e_1 )= L(e_2)$ 1) $(a^*b)^*a^* = (a+b^*)^*$ 2) $(a+b^*)^* = ...
1
vote
1answer
23 views

Difference between regular and not regular languages

I don't understand the difference, in classes I've seen the pumping lemma for regular languages and I know how to apply it to demonstrate whether a language is regular or not, but I feel that I don't ...
2
votes
1answer
41 views

NFA to DFA and Regular Expression

The truth is that my teacher gave us a homework, and I wanted to ask you if I did this right. What I have to do is answer the following questions given the following NFA. Why is this an NFA? What ...
1
vote
1answer
49 views

Find regular expression for a given language

I need to find a regular expression for the following language: $$ \Sigma = {\{a,b,c}\} $$ define $L$ to be the language of all words over $\Sigma$ that contain the substring $aba$ odd number of ...
0
votes
1answer
39 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
1
vote
2answers
33 views

Proving {0^n 1^n 2^n | n >= 0} is not regular

This is not a homework assignment, but something I'm reviewing. I need to prove that $0^n 1^n 2^n$ where $n \geq 0$ is not regular (Just the DFA, not related to CFG). I feel like this is similar to ...
0
votes
1answer
34 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
1
vote
1answer
32 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
0
votes
1answer
38 views

Proving that two expressions are equivalent

So, I'm working through some proof exercises, and one of the questions is about the following regular expression: (a|b)* = a*(a|b)* if they are equivalent, prove ...
0
votes
2answers
33 views

Finding the regular expression

I have the problem below: I need to find the regular expression of the set of strings where $n(a)+n(b)$ is an even number (where $n(a)$ is the number of $a$'s and $n(b)$ is the number of $b$'s) .. I ...
0
votes
0answers
26 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, ...
1
vote
1answer
44 views

Regular expressions

I have this assignment and I have to prove that $$ (b+aa^* b)+(b+aa^* b)(a+ba^* b)^* (a+ba^* b) = a^* b(a+ba^* a)b^* $$ How do I prove this? What I have is this: $$\begin{align} \text{LHS} ...
2
votes
0answers
29 views

Regular expressions and equality

Is the equality true or false? $(r^*s^*)=(r+s)^*$ My Approach: Assume the alphabet used is {0,1}$^*$ Equality is false: If r = 0 and s = 1 Then if 0101 $∈$ $(0 + 1)^*$ this is true because ...
0
votes
1answer
51 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
0
votes
1answer
19 views

Clarification on Lemma problem

I have trouble understanding this question. I have no idea where to start. Let $A$ be the set of palindromes over $\{a, b\}$. Suppose you are trying to prove that $A$ is not regular using the ...
0
votes
0answers
39 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 ...
0
votes
4answers
41 views

Regular Expression for Simple Language

I'm having trouble writing a regular expression given the following $\{a, b, c\}$ which produces the set of strings of length 3. I don't really understand how to restrict the length of the string. ...
0
votes
1answer
88 views

Which of the following sets are regular and which are not? Give justification.

Which of the following sets are regular and which are not? Give justification. a) $\{a^nb^{2m}\mid n\ge 0\text{ and }m\ge 0\}$ b) $\{a^nb^m\mid n\ne m\}$ c) $L((a^*b)^*a^*)$ d) $\{a^nb^nc^n\mid n\ge ...
0
votes
2answers
36 views

Regular expresson a's and b's

Need to construct a regular expression that recognizes the following language of strings over the alphabet {a,b}: - The set of all strings over alphabet {a,b} in which every occurrence of b is ...
0
votes
0answers
24 views

Regex - Ternary number that leaves a remainder of 3 when divided by 4

I need to find the regular expression behind: L = {α ∈ {0, 1, 2}∗ | α leaves a remainder of 3 when divided by 4 and is a ternary number} Any help would be greatly appreciated!
0
votes
1answer
31 views

Regular Expression of alternative 0's and 1's?

Let $L$ be the language of $0$'s and $1$'s in alternate positions, where $$ L = \{ \epsilon, 0, 1, 01, 10, 01010,\ldots\}. $$ Is $(0)*$ + $(1)*$ a valid regular expression that represents this ...
2
votes
1answer
29 views

regex for binary string which doesnt contain 11110

Here's my attempt, although I'm not sure if i missed any edge cases: $(0,10,110,1110)^*(1)^*$ it seems to work for any random string i test in a regex program, but is this correct?
-2
votes
1answer
40 views

What is the Regular Expression for this DFA? [closed]

What is the Regular Expression for this DFA?
1
vote
1answer
10 views

Regular expression building: Comment delimited strings

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

Isn't $L=\{ww|w \in \{0,1\}^*\}$ a Non Deterministic Context Free Language?

My book says that it is not a Non Deterministic CFL. If $ww^R$ can be a N-CFL, then why not the one in the question? I think it might be a printing mistake, not sure.
1
vote
0answers
29 views

Why is $a^nb^n|n\geq1$ not regular and $a^nb^n|n\leq {10^{10}}$ regular?

I've heard somewhere that since the latter is bounded, it is regular. Can anyone explain me what a bound actually means? And if the latter is regular, then how would you write the regular expression ...
1
vote
1answer
102 views

Blocks of Pyramid Pattern Expression [duplicate]

There is a pattern following, and trying to find the algebraic expression Each layer (from the top). Diagram. So the first layer has 1, second has 4, third has 9, and the fourth has 16. That's ...
1
vote
2answers
30 views

Did I find the right expression for the regular language for this FSA?

I have the following FSA, and the regular language that I found for it: Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally ...
2
votes
3answers
49 views

regular language proof, a language partial to a regular one

So, I've been trying to solve a question I got and I think I'm correct but I'm not positive. Is the language {w| www belongs to L' and L' is regular} regular? I couldnt find any way to prove it isnt ...
0
votes
1answer
36 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?
0
votes
1answer
31 views

Binomial theorem - number of terms in expansion

Question: Find the number of terms, after simplifying, in $$(x + y + \frac{1}{x} + \frac{1}{y})^{16}$$ I was unable to find any approach to this question. Fully expanding the expression isn't a ...
1
vote
3answers
22 views

Expression of Equation

Find the next three terms for the pattern following : (-1276),(+425),(-142),(+47) Simple pattern here.... Only pattern I can find is that, the odd number term goes up by 1134, and the even number ...
1
vote
5answers
29 views

Finding expression for pattern

This seems easy.... Pattern: 3, 6, 10, 15, 21.... How do I find expression for this? It looked easy, but I couldn't find it. I tried graphing it, but it turned out that it is not quadratic... ...
0
votes
1answer
19 views

Are regular expressions in mathematics related to PCRE or POSIX regexps?

I've recently come across a number of questions tagged with (regular-expressions), and talking about some type of regular expressions, here's an example of such ...
0
votes
2answers
41 views

Regular expression 00 or 11 not both

Can anyone help me with this question: I know it before, but I have tried to solve it myself and didnt succeed. what is the regular expression for this language: L=all words that have 00 or 11 but not ...
-1
votes
1answer
45 views

Regular expression with xor [duplicate]

Can anyone help me with this question: I know i asked a similar question not a while ago but i'm not able to understand how its possible. If anyone could give me a lot of examples instead of an ...
0
votes
1answer
21 views

Regular expression problem

I have this question and no clue how to solve. Thanks for your help I need to build the regular expression matching this language $$L=\{ 0^m~1^n | (m+n) \pmod 3 = 1 \}$$
0
votes
1answer
63 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 ...
0
votes
2answers
32 views

Arithmetic Progressions Formula

I'm studying progressions in math class in Portugal, and I don't know the words/translation in english for certain things so I'll try to explain. I have this arithmetic progression: 2, 8, 18, 32 ... ...
1
vote
1answer
50 views

For any regular expression for a finite automata, how do you find the shortest word accepted?

So in the question "For the following regular expression α over the alphabet {a, b}, find one of the shortest words in the language L(α) defined by this expression" a*abab* As far as I understand, ...
2
votes
2answers
174 views

Combinatorics problem involving a regular expression

If formal definition of a regular expression is required, please comment and I'll add it. I was given the assignment of determining how many words of length $n$ can be produced from a regular ...
1
vote
0answers
18 views

Equality of regular language

I am showing that two regular expressions are equal. In one of intermediate steps, I thought of the equaility: $$(RS+R)^* = (RS)^*R(RS)^*R(RS)^*....R(RS)^* = R^*(RS)R^*(RS)...R^*$$ Is it true? I ...
0
votes
1answer
43 views

How do I generate regular expression from this deterministic finite state automaton?

I want to create a regular expression from the following deterministic finite automaton: "abb" substring search How do I generate regexp from above dfa and what are the steps for doing so? ...
1
vote
1answer
35 views

Instead of mid-point, how do i find a third of the way up the line instead.

I'm working with the program Maya, and i need to script a way to find various fractions up a line for each 3D vector. For example, lets say I have the vector (0, 0, 0), and the vector (12, 12, 12). ...
0
votes
1answer
36 views

I don't understand the value of the following regular expressions.

$$\begin{align} 0^{*}10^{*} &= \{w ~\mid ~ w \text{ contains a single } 1\} \\ \Sigma^{*}1\Sigma^{*} &= \{w ~\mid ~w \text{ has at least one } 1\} \\ 0 \Sigma^{*}0~\cup ~1\Sigma^{*}1~\cup ...
0
votes
1answer
31 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
0
votes
1answer
21 views

converting to regular expression

{w | w can be written as $0^k l 0^k$ for some $k \geq 1$ and for any $l$ in ${0,1}*}$ i.e. 00010111000 can be written as 0^3 10111 0^3 How can I convert this description into a regular expression? ...
2
votes
1answer
29 views

Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...