The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
4answers
747 views

Why isn't this a regular language?

I'm stuck as to figuring out why $L_1$={$n^p$ | $p$ = a prime number} is not a regular language but $L_2$={$n^p$ | $p$ = a prime number bounded by some fixed number f} is. I can see that $L_2$ is a ...
1
vote
2answers
56 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 ...
25
votes
6answers
2k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
4
votes
3answers
198 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
4
votes
3answers
1k views

Application of Pumping lemma for regular languages

I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular. According to the Pumping lemma for each regular language a word $w = xyz$ exists, that ...
2
votes
4answers
4k views

Intersection of two deterministic finite automata?

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
1
vote
1answer
93 views

Possible solution for Sipser 1.63

Sipser's question 1.63: Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets. Is my solution correct? Since $A$ is infinite and ...
1
vote
1answer
292 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
2
votes
2answers
238 views

Pumping Lemma Excercise

I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ...
2
votes
2answers
44 views

Why is $S(L)$ regular?

Let $L$ be a regular language, and $\Sigma$ be its alphabet. Then, the language $S(L) = \{y \in \Sigma^*~|~xy \in L \text{ for some string }x \in \Sigma^*\}$ is also regular. I am trying to ...
1
vote
2answers
20 views

FSM to be regular with atleast two 0's and at most two 1's

Is it possible to construct a FSM to prove that the set $X$ is regular, where $$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$
1
vote
1answer
55 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
1
vote
3answers
2k views

Formally prove that every finite language is regular

I know how to prove this informally, but don't know what the formal proof should look like.
1
vote
1answer
789 views

Showing that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Thanks in advance. Let $Σ = \{0, 1, +, =\}$ and $\mathrm{ADD} = \{x = y + z \mid x, y, ...
1
vote
2answers
194 views

Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(
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
2answers
97 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
0answers
58 views

Binary regular language?

Given $m,n∈Z$, $A=\{a,b,c\}$ is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this binary language $L$ regular over $A(2,\$)$ ( i.e.$\{A∪\{\$\}\}\times ...
0
votes
0answers
41 views

Regular language?

Is the binary language $L=\{(a^2,a)\}^*=\{(a^2,a),(a^4,a^2),(a^6,a^3)...\}$(a subset of $A^*\times A^*$,with $A=\{a,b,c\}$ a finite alphabet set) is regular over $\{A∪\{\$\}\}\times ...
0
votes
1answer
151 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
0
votes
1answer
76 views

Algorithm for checking if regular language has given property

Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property: $$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq ...
0
votes
3answers
1k views

Is there a subset of a non regular language that is regular

I am just curious is there any non regular language whose subset is regular?