The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
19 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
22 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
0answers
11 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
27 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
0answers
25 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
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
25 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
12 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
41 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 ...
0
votes
0answers
28 views

Discrete Math — Regular Expression to express an infinite string of same character?

How might I write an regular expression to represent an infinite string of 1's? In other words, I want an RE to accept 1111... 1* doesn't do the trick because it also contains finite strings of 1's. ...
4
votes
1answer
25 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 ...
5
votes
2answers
63 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
1answer
20 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
44 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
28 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
59 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
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}.
2
votes
0answers
35 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
311 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
20 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
39 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
15 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
27 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
25 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
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 ...
1
vote
2answers
73 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
99 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
45 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 ...
1
vote
1answer
170 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
80 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 ...
0
votes
3answers
138 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 ...
6
votes
2answers
961 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 ...
0
votes
1answer
18 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
vote
1answer
47 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
votes
1answer
38 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
25 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
34 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
39 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
31 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
99 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
31 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
2answers
67 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
788 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 ...
0
votes
1answer
248 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 ...
2
votes
1answer
412 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 ...
4
votes
0answers
51 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
2answers
102 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. ...
0
votes
1answer
95 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
47 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$ ...