The tag has no wiki summary.

learn more… | top users | synonyms

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 ...
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 ...
1
vote
2answers
334 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
52 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
38 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
31 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
45 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
49 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
58 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
45 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
371 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
156 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
82 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
273 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?
1
vote
1answer
35 views

Regular Expression that accepts a language L

Given, $L=\{ x \in\{0,\,1\}^* | x=0^n1^m \text{ and }n+m\text{ is a multiple of }3\}$ give a regexp that accepts the language. My thoughts are: $(000)^*(\epsilon + 001 + 011)(111)^*$ Is this right? ...
0
votes
1answer
130 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
0answers
331 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 ...
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
36 views

Myhill-Nerode Theorem with constraint

I am trying to to understand the Myhill-Nerode Theorem with the example. $L = \{{0^i1^j}|\ j > i\}$ I have read some article but still cannot fully understand,what I know about is that I have to ...
0
votes
1answer
71 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
37 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 ...
1
vote
1answer
102 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 → ...
0
votes
1answer
120 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. ...
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 ...
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 ...
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 ...
0
votes
2answers
87 views

Proving that a regular expression belongs to a certain language

I've often come by questions that require proving that a certain regular expression belongs to that language. Example: Given $\Sigma = \{0,1\}$, and the language $L$ of all the words that have ...
1
vote
2answers
129 views

Translate from logical formula to regular expression

I want to translate this formula in a regular expression: Explanation: The alphabet is : $\{a, b, c\}$ $w(p) = a$ , means on the position $p$ in the word stands an $a$. For the regular ...
1
vote
1answer
143 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
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
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 ...
5
votes
1answer
546 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 ...
0
votes
1answer
195 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 ...
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...
2
votes
1answer
104 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, ...
0
votes
1answer
36 views

$L$ is a class of languages that cannot be represented by a regular expression. How to state cardinality of $L$.

$L$ is a class of languages that cannot be represented by a regular expression. The book says that the cardinality of $L$ is $2^{\aleph_0} > \aleph_0$ what's the logic behind getting the ...
0
votes
1answer
30 views

$L = L\bigl((b \cup ab \cup aab)^*(\lambda \cup a \cup aa)\bigr)$ . how does $bbbbbbabaabaa$ belong to L?

Let $L$ be the language generated by the regular expression $(b \cup ab \cup aab)^*(\lambda \cup a \cup aa)$. how does bbbbbbabaabaa belong to L? I know $(b \cup ab \cup aab)^*$ can be translated to ...
0
votes
1answer
89 views

L = (aa)*(bb)* checking if a string belongs to L* but not to L

L = (aa)*(bb)* checking if a string belongs to L* but not to L the string is: aabbaa I can't grasp the concept of putting a * (kleene star) on L, which already has a kleene star in it's definition. ...
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 ...
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 ...
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 ...
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
1answer
105 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
1
vote
1answer
46 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
28 views

Converting regular expression to NFA.

I have the following two regular expressions and I need to convert them to NFA diagrams. I already did some and was wondering if they made any sense...i hope I'm not confusing the signs. ...
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
1
vote
1answer
218 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
2answers
243 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) ...
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 ...