The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
319 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
2answers
40 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
0
votes
2answers
63 views

Algorithm for a regular expression

This was a question for an exam that I received 0 points on, I'd like to get some input on what the correct answer should have been. Imagine that you are asked to write an algorithm P that takes a ...
2
votes
1answer
55 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 ...
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
47 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 ...
1
vote
1answer
28 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
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 ...
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 ...
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
1answer
43 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
129 views

induction to prove regualr expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
0
votes
1answer
36 views

Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$

Can someone provide me a Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$ eg $S$ is a 3x3 matrix with [6 8 5 ; 3 4 6 ; 9 0 5] where $n$ = 9 (elements) and I need to ...
0
votes
1answer
119 views

Construction of Regular Expression

I have the problem of needing to construct a regular expression corresponding to the set of strings of 0's and 1's whose number of 0's is divisible by five and whose number of 1's is even. ...
0
votes
1answer
188 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 ...
0
votes
1answer
22 views

Need help with the steps

Tried this problem several times and still cant get the right answer. Please help! https://webwork2.uncc.edu/webwork2_files/tmp/equations/ba/00ebd18c83856ce9c3b184a9a058a01.png
0
votes
1answer
78 views

Is this NFA correct?

For the language L = $\{\Sigma^*. 0 .\Sigma^5 . 1. \Sigma^*\}$ The NFA must have 8 states. Also, what would be the upper bound on the number of states of a DFA recognizing L.
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 ...
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 ...
2
votes
0answers
150 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
vote
0answers
36 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
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
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$?
1
vote
0answers
41 views

Calculating the variance of the a regular expression assuming position dependent

Hello I am having trouble with a slightly biological problem I am given a regular expression $- [RK]-[LV]-[DE]-x(2)-Y$ this expression means that there is a string with the first position being an ...
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}.
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
0answers
25 views

Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$?

Let $L_1,L_2,L_3$ be languages, Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$? After a half an hour of trying to disprove it, I've decided my intuition might be wrong. ...
0
votes
0answers
24 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 ...
0
votes
0answers
30 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
0answers
330 views

Palindrome Decidable by DFA

Here's a problem a professor I was talking with gave to me to see how people solve. How would you solve this? A string in {a,...,z}* is said to be a palindrome if it is equal to its own reversal. Is ...
0
votes
0answers
53 views

Regular expression of: $\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}$.

Given $\Sigma = \{ 0,1,2 \}$, write a regular expression for $$\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}\;.$$ I know how to do a regular expression for a language that does ...
0
votes
0answers
24 views

regular expression length $\ge3$

my note says the length of the following reg expression is $\ge3$. $$((a\cup c)\cup b(a\cup c)\cup bc(b\cup c))(a\cup b\cup c)^*$$ I don't think it's $\ge3$ because: $$((a\cup c)\cup b(a\cup c)\cup ...
0
votes
0answers
37 views

Homework problem with expressions.

I am doing homework and I have multiple choice question that states which are the valid expressions. $bb \Phi a^*$ $(aa)^+ b(a+b)^*$ $\Phi (a+b+c)^*$ $ba^nbb: n>0$ $\lambda (a+b)^*a(bb+a)$ ...
0
votes
0answers
18 views

Method for Evaluating expressions with mixed operations and grouping symbols?

What is the Method for Evaluating expressions with mixed operations and grouping symbols?
0
votes
0answers
403 views

regular expression and intersection

I have this language L that contains only one string: $a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3}a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3} ....a_{n}...a_{n}$ written more concisely ...