Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.
Questions tagged [regular-language]
1253 questions
0
votes
1 answer
Determining if language is regular?
Let $R$ be a regular language and $R_e := \{w\ |\ w \in R \text{ and the length of } w \text{ is even}\}$
Question: Is $R_e$ regular? Prove your answer.
I am having trouble with these type of questions. Can anyone help?
a b
- 21
0
votes
2 answers
Is this a regular language ? SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2}
Question:
Define the following operation:
$$\text{SubString}(L_1, L_2) = \{w \mid \exists x, y \in L_1, xwy \in L_2\}$$
Let $L_1$ be any language, and $L_2$ regular. Prove that $\text{SubString}(L_1, L_2)$ is regular.
Thoughts:
I need to somehow add…
jreing
- 3,297
-1
votes
1 answer
Is every language with a single letter alphabet is decidable?
I'm studying for an exam in theoretical informatics. I have a question for which I can't find an answer.
Is every language with the following alphabet decidable:
∑ ={1}
I need to explain why it is or isn't.
-1
votes
1 answer
Prove that a binary language is not regular by using the fact that the binary language of palindromes is not regular without using Pumping Lemma.
Note: This is not a repeat question. There is another questions very similar to this posted, but that uses the Pumping Lemma.
A binary language of all binary strings that are palindromes $L_1$ is not regular. Use this fact to prove that $L_2$…
Tommy
- 27
-2
votes
2 answers
Regular expressions creating language m
Construct a regular expression that defines the language M (say) containing all words beginning with
exactly one a or exactly one b. (Words in M are at least of length 1 and words such as aa, bbbaba and
aaaabbabbbabb do not belong to M. Words in M…
