The tag has no wiki summary.

learn more… | top users | synonyms

21
votes
9answers
709 views

Farewell 2014 welcome 2015 - “Math Golf”

In programming, Code Golf is a competition in which the participants are trying to implement an algorithm with code which is as short as possible. Also, Stack Exchange has a site dedicated to Code ...
0
votes
1answer
339 views

Complement of a regular expression?

What is the regex for the complement of $r = b^*(ab + a^* + abb(b^+))^*$ ? I am thinking $(a+b)^*(abb)^+a^* $ since anything that contains $abb$ and is not followed by $b$'s would not be accepted ...
1
vote
1answer
284 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 ...
2
votes
2answers
31 views

What is the difference between Algebraic Expressions and Polynomials?

Both are a combination of terms grouped together. What is the difference?
1
vote
2answers
20 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
18 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
35 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
20 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
26 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
19 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
24 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... ...
-1
votes
1answer
37 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
0answers
32 views

Express $y$ in terms of $x$

After solving some differential equation I arrived at $$2ln(y-1) +(y-1)=(x-3)+3 ln(x-3)+c$$ but I can't write $y$ in terms of $x$ to find explicit solution.
0
votes
1answer
17 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
30 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 ...
0
votes
1answer
20 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
27 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, ...
2
votes
2answers
889 views

How can concatenating empty sets (languages) result in a set containing empty string?

In the book "Introduction to the Theory of Computation" by Michael Sipser, in the section 1.3 Regular Expressions: The symbol ε represents the emty string, which may be a valid element of a language: ...
0
votes
0answers
8 views

find the intersection of two regular expressions

I have a language A which is described as $a^*b+c^*$ in which the alphabet is $\{a,b,c\}$. I define a new language which is: $A_{1/3}=\{xz|xyz \in A , |x|=|y|=|z|\}$. I want to find the intersection ...
0
votes
1answer
32 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
23 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
37 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, ...
1
vote
1answer
40 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
2
votes
2answers
161 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
13 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
31 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
27 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
2answers
76 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
0
votes
0answers
15 views

Expressing sets as regular expressions

Express each of these sets using a regular expression: (a) the set of strings of one or more 0s followed by a 1 (b) the set of strings of two or more symbols followed by three or more 0s My answers ...
0
votes
1answer
30 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
18 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
26 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 ...
0
votes
0answers
13 views

DFA automata theory

find the regular language for w contains abb but not abbb. I started with (a* abb a*)* (lambda + ab)* is it right ?? sorry i don't know how to write lambda in symbol.
0
votes
3answers
48 views

Rewriting an expression

I got the following problem and can't solve it. Factorize the following statement: C(n+2, n) + C(n+3, n+2). So basically they are asking to rewrite the expression as a X*P expression instead of A+B ...
2
votes
1answer
31 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
0
votes
1answer
24 views

Proof the 1 language is contained in another

Does anyone know what the best method is to prove that the intersection of Language1 and Language 2 = Language1? Where both languages are over alphabet {a,b,c}.
0
votes
1answer
28 views

Intersection / Union of two regular expressions

Is there a way to directly form a new regular expression when given two regular expressions and the desired operation (Union or Intersection). $$ (a+b)^*aa(a+b)^*\cup (a+b)^*aa(a+b)^* $$ $$ ...
0
votes
2answers
50 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
0
votes
1answer
358 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
1
vote
3answers
134 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
0
votes
1answer
29 views

Solving an Equation for a Variable with $\max()$ and $\min()$ Functions

I came across an expression in 3 variables involving the max and min functions: $$x = y - \max(x,z) + \min(x,y,z).$$ I need to solve this expression for $y$. Is there any way we can do this? ...
1
vote
2answers
285 views

Converting from NFA to a regular expression.

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows $$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) ...
1
vote
2answers
71 views

Substitutions in Maple

Can any one tell me what am I doing wrong in the following expression in Maple? subs(a*b*c=A, e*f/d=B, a*b*c*e*f/d) I am getting the output $\frac{abcef}{d}$ ...
0
votes
1answer
675 views

regular expression that dont have both substrings bba and abb

All the words that dont have both the substrings bba and abb ‘words that do not have both substrings…’ means that words may have one or the other - just not both (i.e. not abba or bbaabb). I tried ...
0
votes
3answers
155 views

What is the difference between regex operations in math and regex in UNIX / Linux?

What is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
0
votes
1answer
83 views

Confusion about the generating function for a regular expression

Given a regex A = (a*b)*, I want to compute the Generating Function that enumerate this regex. The formula for the GF of that regex is ...
2
votes
0answers
43 views

how to covert regular expression in simplest form?

I have made this expression from nfa (NFA to regular expression) : (a+ab+aa*b)*(a+a*a) but at book answers it is written like this : (a+aa*b)*(a*a) I am thinking that the my answer is same as ...
1
vote
1answer
326 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
0
votes
1answer
21 views

Which is true about this NFA?

Let $M$ be an NFA with alphabet {0,1} that accepts every binary string. Which of the following is true? a) Every state of $M$ must be an accept state b) $M$ does not have any accept state c) The ...
0
votes
2answers
42 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 ...