The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
2answers
735 views

Express y in terms of x

Question: $$ \text{It is given that } y= \frac{3a+2}{2a-4} \text{and }x= \frac{a+3}{a+8} \\ $$ $$ \text{Express } y \text{ in terms of } x. $$ From using $x$ to solve for $a$, I discovered that ...
5
votes
1answer
542 views

Freshening up on discrete math (regular expressions)

I'm trying to freshen myself up on discrete math( I forgot a lot). I know this is a trivial question and not worth your time. But I forgot how to solve problems involving formal language theory. For ...
4
votes
0answers
43 views

How to write a regular expression?

I am trying to write a regular expression for the set of all strings in Σ* that starts with an even number of b's and contains at most two a's. The language contains only a's and b'. This is what I ...
3
votes
4answers
121 views

How does one show that these two expressions are the same?

I tried to compute the value of $\sin 75^\circ$ using the sine of standard values $(30^\circ, 45^\circ...)$ and did it by two ways. One, by expanding $\sin (45^\circ+30^\circ)$ and the other by ...
3
votes
5answers
80 views

Expression for a bounded function

I have a bounded function, $$ y= \begin{cases} 1 & \text{if $x>1$} \\ x & \text{if $0\leq x\leq 1$}\\ 0 &\text{if $x < 0$} \end{cases} $$ Does anyone ...
3
votes
1answer
474 views

Regular Expression Proof

I am trying to prove the following statement: If $S$ and $T$ are any regular expressions over a 1-letter alphabet and if $n$ is a natural, then the languages $(ST)^n$ and $S^nT^n$ are equal.
2
votes
2answers
59 views

Regular expressions, is it always true that (r+s)*=r*+s*?

I'm really confused about this, can some one please help me understand this better. If r and s are regular expressions then is it always true that (r+s)=r+s*? Are r and s sets and does the plus ...
2
votes
2answers
122 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
2
votes
2answers
111 views

Basic regular expressions problem

I'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular ...
2
votes
1answer
650 views

Is one regular language subset of another?

Let $L_1$ and $L_2$ be two regular languages given as regular expressions (in this type of tasks it often happens that $L_1 \subseteq L_2$, but vice versa it is false). Is there a nice way to ...
2
votes
1answer
31 views

Finding the mistake in a new way of generating FSMs from regular expressions

As described e.g. here (see pp. 2-3) a final state machine can be easily constructed from a regular expression. For the union of to expressions $e + f$ I need to look at the original way of ...
2
votes
1answer
26 views

Equivalence of two regular expression

I have a quick question to ask. So I am trying to come up with a regular epxression which represent a language over {a,b} that contains at least one 'b' in it. I came up with this: $$(a| b)^*b(a| ...
2
votes
1answer
33 views

Is the language L regular?

Could you tell me if the language $L=\{a^ib^j:i+j=k, k \geq 2 \}$ is regular? Do I have to find a regular expression for this language? Or what can I do to check if $L$ is regular or not?
2
votes
1answer
56 views

Regular expression for language

Let's have a language $L=\{\omega\in\{a,b,c\}^* | \omega $ contains $ab$ and does not contain $ba\}$ make a regular expression for this language. I've ended up with this one ...
2
votes
1answer
29 views

Regarding regular expression. why do the following strings not exist in the expression.

Let L be the language defined by the regular expression: (a U b U c)((ab U ac U b)*(a U b) U (aa)*) the answer book says that 'aaaa' and 'aaaaaa' do not belong to L. I can show that aaaa and aaaaaa ...
2
votes
2answers
41 views

Regular Expressions Help [duplicate]

I need a little help with Regular Expressions. The allowed operations are obviously + (union) , * (Kleene star) and concatenation. I have to write Regex for the following 2 examples. I have tried a ...
2
votes
1answer
133 views

Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
2
votes
1answer
103 views

L is language generated by the context free grammar G = (V, $\Sigma$, P, S)

L is language generated by the context free grammar G = (V, $\Sigma$, P, S), where $\Sigma$ = {a,b,c}, V = {S, A, B}, and the production set P is: S -> aSb | A A -> cAb | B B -> cb My question is, ...
2
votes
2answers
75 views

For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct?

For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct? $(a+b)^+$ . Which is $(a+b)$ to the power of $+$ which I think accepts all combinations of ...
2
votes
1answer
210 views

Constructing finite state automata corresponding to regular expressions. Are my solutions correct?

I have drawn my answers in paint, are they correct? (4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions: (i) 0 My Answer 4ci (ii) ...
2
votes
0answers
19 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 ...
2
votes
2answers
41 views

Regular Expression Notation

I'm doing a theory of computation course and can't for the life of me find any good resource that will tell me how a regular expression such as (a+b)* converts to set form. I've thought of a binary ...
2
votes
1answer
57 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 ...
2
votes
0answers
155 views

Regular Expression For Set of Strings Not Containing OOO

The following is my attempt at coming up with a regular expression for the set of binary strings that do not contain $000$: $(1 + 01 + 001)^*(\epsilon + 0 + 00)$ I'm going to need it for a ...
2
votes
1answer
145 views

Number of distinct strings in regular expression

Given the regular expression (1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 ), how many distinct strings would this evaluation produce? How is the word "distinct" ...
1
vote
2answers
242 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
23 views

Regular expression translation.

Given a set {1,2,...9} how can I construct a regular expression starts with a 3 has no 8's and has even number of 6's? Here's what I tried: $$$$ Define a new set no8 = {1,2,3,4,5,6,7,9} ...
1
vote
2answers
54 views

Strings: X^0 confusion

I've been given the set of string: X = {2,00}. I've been asked to perform various concatenation operations on it. ...
1
vote
1answer
312 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
1
vote
2answers
40 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}$ ...
1
vote
1answer
271 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 ...
1
vote
1answer
59 views

find a regular expression for a given language

It is given that $\Sigma=\{1,2,4,5,7,9\}$ and $L=\{w: w \in \Sigma^{*} \text{ ,w gets divided completely by }5\}$. Could you help me to find a regular expression for this language?
1
vote
2answers
707 views

Converting to regular expressions

I am really not sure about the following problem, I tried to answer it according to conversion rules the best I can. I was wondering if someone can give me some hints as to whether or not I am on the ...
1
vote
1answer
26 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$ ...
1
vote
1answer
100 views

Check if a regex is ambiguous

I wonder if there is a way to check the ambiguity of a regular expression automatically. A regex is considered ambiguous if there is an string which can be matched by more that one ways from the ...
1
vote
1answer
53 views

About described DFA

I need to find DFA (or NFA, $\epsilon$-NFA, it's not improtant (I know how to convert between them)) that accept all strings of $0$'s and $1$'s such that every block of five consecutive symbols ...
1
vote
1answer
101 views

Translate a regular grammar to a regular expression

I want to translate the following grammar into a regular expression: Set of variables V := {S,T} Set of terminals Σ := {a,b} Set of relations S → "" S → aS S → bT T → ...
1
vote
1answer
56 views

Question about Regular Expressions, DFA and relations

I have a few questions about discrete math, I can't fully grasp these concepts. For regular expression, what does the U symbol mean, at first I thought it meant that it was similar to or, for example ...
1
vote
2answers
50 views

Is $\{w \in \Sigma ^* : |w|_2 mod 4 = 2\}$ a regular language?

Given alphabet $\Sigma = \{1,2,3\}$, is $\{w \in \Sigma^* : |w|_2 \bmod 4 = 2\}$ a regular language? I tried so hard on finding a regular expression but couldn't...
1
vote
1answer
41 views

set of all reg exp vs set of all languages

$\Sigma$ = {a,b,c,d,e} V = {A,B,C,D,E,F,G,H} According to the notes: The set of all regular expressions over $\Sigma$ is infinite and countable. The set of all languages over $\Sigma$ is infinite ...
1
vote
1answer
217 views

Counting number of strings that contain substring matching Regular Expression

I have regular expression R, and I want to find F(n) is the number of strings of length n that strings that contain substring matching Regular Expression. Suppose the alphabet-size is M. We can apply ...
1
vote
1answer
85 views

Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
1
vote
2answers
49 views

Regular languages question

Describe these languages over $\Sigma={a,b}$ $\Sigma^{*}(a\cup\epsilon)b^*$ $a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^{*}a\Sigma$ Just making sure I understand some basic concepts... First one ...
1
vote
1answer
72 views

Proving or disproving regularity of a language

The question is as follows: If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular My intuition says that it's wrong so I've been looking for a ...
1
vote
1answer
100 views

Are these all the strings that the regular expression (a* + b*) . (a.b)* accepts or am I missing some?

From what I understand the regular expression (a* + b*) . (a.b)* accepts the following strings: Empty string, aaaaaaaaaababab, bbbbbbbbbbabab, aabab, babab, etc with different lengths of a, b and ab. ...
1
vote
1answer
220 views

Negate regular expression

Suppose I have a simple regular expression describing a language like $(a+b)^* a?b (a+b)^*$ (a language in $\Sigma = \{a,b\}$ consisting of all words with substring $a?b$). I haven't found a general ...
1
vote
1answer
186 views

Transformation of a regular expression

Let $a,b,c$ be regular expressions. Prove by transformation that $$(a^*b^*+c)^* \equiv (a+ (b+c)^*)^*$$ I tried to start with the second term $$(a + ((b+c)^*))^* = (a^*(b+c)^*)^* = ...
1
vote
1answer
54 views

Prove or disprove whether the following is a regular language

I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ...
1
vote
1answer
43 views

Checking some Regular Expression problems

I'm given the alphabet $$ \Sigma = {\{a,b}\} $$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ...
1
vote
1answer
31 views

Pumping Lemma Squares Proof Explanation

I'm looking for some help understand this perfect squares proof using the pumping lemma. Here is the proof: I don't understand how n^2 + k < n^2 + n towards the end of the proof. Would anyone ...