The regular-language tag has no wiki summary.
5
votes
3answers
346 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 ...
23
votes
5answers
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
129 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) ...
3
votes
2answers
605 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 ...
1
vote
1answer
216 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 ...
1
vote
2answers
115 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
3answers
563 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.
