The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
57 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
347 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
97 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
162 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
1k 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
19 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
50 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
41 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
30 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
38 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
44 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
36 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
116 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
37 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
74 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
1k 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 ...
1
vote
1answer
373 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
676 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
60 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
114 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
105 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
48 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
41 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
1answer
25 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
1answer
44 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
48 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
344 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
vote
1answer
36 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
votes
1answer
48 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 + ...
0
votes
1answer
64 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?
0
votes
1answer
707 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 ...
3
votes
5answers
83 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 ...
2
votes
2answers
59 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 ...
0
votes
1answer
80 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
0
votes
1answer
35 views

Is this a regular language? Number of a's greater than $k$

Prove/disprove: $L = \{ w \mid |w|_a \geq 2k \}$, where $\Sigma = \{ a,b\}$ and $k$ is a constant, is a regular language. Intuitively I am saying yes, it is a regular language. But I don't ...
1
vote
1answer
155 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 ...
0
votes
0answers
27 views

productions with identical right hand sides for different nonterminals

Can a regular grammar contain two productions with identical right hand sides? I know in context free grammars shift reduce parsers issue reduce reduce conflicts when smth like this happens. What are ...
2
votes
1answer
68 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
2answers
1k 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
1answer
53 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
0
votes
1answer
40 views

Prove equivalence of two regular expressions.

I am wondering if there is a standard way to prove that two regular expressions are equivalent. I have tried to prove, given two regular expressions $r$ and $s$, that $L(r) \subseteq L(s)$ and $L(s) ...
0
votes
0answers
36 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
0
votes
1answer
65 views

Which strings belong to the regular set represented by the regular expression (1∗01∗0)?

I know the string should be like 1…101…10, but not sure how to describe it. Can anyone help me?
1
vote
1answer
73 views

Complement of a Set of Strings in a Language

Suppose $B= \{ 0^n1^m2^{n-m}:\, n\ge m\ge 0 \}$ Is the complement $\overline B = \{ 0^n1^m:\, 0\le n\lt m\}$? Or is it the universe of all possible strings (including all strings with symbols ...
0
votes
1answer
71 views

Proving Equivalence of DFA and NFA

Im trying to learn Equivalence of DFA and NFA.The problem is that in the below explanation Q' is given as the power set of Q.But this statement seems to be contradictory to the previous statement ...
0
votes
1answer
61 views

Find Regular Grammar from NFA

I'm currently doing some self study to improve my half-forgotten college theory of comp skills. I'm going over some problems from an old book and it asks you to find a regular grammar for the ...
0
votes
1answer
849 views

Build regular grammar from regular expression

Is there an algorithm for creating a regular grammar directly from a regular expression? All the discussions and notes I found so far go through an intermediary step of creating an FA for the reg ex ...
2
votes
0answers
206 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 ...
-1
votes
2answers
95 views

Deterministic Finite Automata with finite strings

How could I prove that every language with a finite number of strings is the language of some DFA?
0
votes
1answer
418 views

Set of Binary Strings Corresponding To a Regular Expression

$(1 + 01)^*(0 + 01)^*$ I'm thinking {set of all binary strings} $-$ {set of binary strings that begin with 00 and contain 11} Would this be correct?