The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
240 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
320 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: ...
1
vote
2answers
36 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
350 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
92 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
80 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
17 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 ...
0
votes
0answers
19 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}.
1
vote
1answer
269 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
18 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
35 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 ...
0
votes
1answer
13 views

Finding a Regular Expression with a Specific Length from a language

Given this language, I was supposed to find the Regular Expression that represented it. Having given up and getting the answer later (below) I couldn't understand the regular expression. Given ...
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} ...
0
votes
1answer
18 views

Regular expression construction.

I would like to construct a regular expression of length at least 5 that starts with 'f' and ends with 'y' and who's second symbol is 'u' from the alphabet {a,b,...,z}. My solution to this problem ...
2
votes
2answers
40 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 ...
1
vote
2answers
63 views

Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
1
vote
3answers
67 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 ...
1
vote
0answers
37 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 ...
5
votes
1answer
530 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 ...
1
vote
1answer
75 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 ...
1
vote
1answer
52 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 ...
6
votes
2answers
729 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 ...
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-) ...
0
votes
1answer
16 views

Regular expression for a particular language

Several years ago I came across a paper that defined a regular expression (or collection of regular expressions?) for a specific language. The language is the language of set partitions enumerated by ...
-1
votes
1answer
36 views

Calculate the following expression value (Complex Numbers)

Hi the following is the equation to solve which I am lost as I do not quite understand the method of using complex numbers to solve. Please help! $ \sqrt[4]{\frac{-18} {1+i\sqrt{3}}} = \frac ...
0
votes
1answer
24 views

Question about Notation in a Regular Language

I am a little confused about the following notation: $L' = \{xy|x\in L \ , y\in L^R\}$. I think this expression is not equivalent with palindrome but I am not entirely sure. For example, I think the ...
1
vote
0answers
30 views

Example of a Regular Map

I am working with Shafarevich's "Basic Algebraic Geometry 1". Example 1.15: The map $f(t)=(t^2,t^3)$ is a regular map on the line $\mathbb{A}^1$ to the curve given by $y^2=x^3$. I am not ...
1
vote
2answers
36 views

Prove by induction on a string

I want to practice proving the following: Given a binary string s, I want to prove $s$ has the same number of substrings 01 and 10 $\iff$ the first and last character of $s$ is the same. For ...
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| ...
0
votes
1answer
52 views

find a regular expression and FA that each define L1 ∩ L2

from the following pairs I am trying to find a regular expression and FA that each define ...
0
votes
1answer
27 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
0
votes
1answer
89 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 ...
0
votes
2answers
52 views

Regex for strings with at least three unique characters

I'm trying to represent some string conditions in terms of regex. One of those conditions I find hard to transform is that the string must have at least three different characters. So is there any ...
0
votes
2answers
421 views

Regex for strings with no three identical consecutive characters

I wanna ask what the regular expression for the strings having the property in the title should be. For binary string with no three consecutive 0, it's quite a simple regex ...
2
votes
1answer
118 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 ...
0
votes
2answers
89 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
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 ...
0
votes
1answer
89 views

how did they get this answer for the words that don't have bba and abb?

I am looking at the answer in solution manual which asked , ...
0
votes
1answer
44 views

Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
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$ ...
0
votes
0answers
40 views

Regarding Regular Expressions and Closure Properties.

I have a question about regular expression and closure properties. Context - I have an homework question asking to prove: a*(b + ab*) = b + aa*b* I think, I know how to get it, what I want to make ...
0
votes
1answer
21 views

Regular Expression Reading

I'm trying to figure out what this regular expression reads as. The regular expression is the following: (0(1 + 2) * 00*) (+ = union) (* = zero or many). I believe this reads as: 0 concatenated ...
1
vote
0answers
33 views

Which is a regular expression for the language?

Could you give me a regular expression for the language that contains at least once the substring $aba$ and at least once the substring $bab$?
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?
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 ...
0
votes
1answer
43 views

Expressions for $(AB)^R$, $(A \cap B)^R$, $(A \cup B)^R$

For any language A, let $A^R$ be $\{x^R \mid x \in A\}$. Then, for arbitrary languages $A$ and $B$, explicitly write down the expressions for $(AB)^R$, $(A \cap B)^R$, $(A \cup B)^R$. I am not really ...
0
votes
2answers
316 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
-1
votes
1answer
42 views

Finding the wrong regular expression

Which one of the following regular expressions does not define the language of all strings that ends with a. $(a + b)^*a$ $b^*aa^*(bb^*aa^*)^*$ $[a(ba)^* + b(ab)^*](a + b)^*a$ $(b + aa^*b)^*a(a + ...
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?
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 ...