Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1
vote
1answer
25 views
Which word could I use for the pumping lemma?
I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma.
Task:
Be
$\sum { =\left\{ a,b,c \right\} } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \...
2
votes
1answer
43 views
How to prove a language is not regular using the Pumping Lemma?
I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.
Task:
Prove that $M = \left\{ a^...
0
votes
0answers
21 views
Finite State Automata for English regular main verbs
I would like to build an FSA to recognise english regular main verbs. E.g. walk, play, call, look, etc... with following morphological forms: (1) base form, (2) third person singular (-s), (3) present ...
1
vote
1answer
27 views
is $0^x1^y$ context-free?
given that L is regular, does the following make a context-free language?:
i) $\{0^x1^y \mid 0^{x+y} \in L\}$
ii) $\{0^x1^y \mid 0^{x-y} \in L\}$
since L is regular, i presumed that i) can be put ...
0
votes
2answers
30 views
Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?
My book states that the language
$$L_1 = \{a^nb^n\mid n\geq 1\}$$
is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really ...
1
vote
1answer
16 views
Can Non-Linear Grammars generate Regular Language?
I stumbled upon the following non-linear grammar
$$S \to AB$$
$$A\to aaA\mid \epsilon$$
$$B \to Bb\mid \epsilon$$
and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} ...
-1
votes
0answers
22 views
Give an example of a context-free language that is not regular, or prove that none exists [duplicate]
Is it pda? how can I solve this question?
0
votes
0answers
20 views
How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]
I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
0
votes
1answer
39 views
What do I need to show that music theory is a reugular language not a singularity? [closed]
After writing a lot of tablature, it is obvious to me music is a regular language but I can't find anything in the literature so I am trying to understand what other people consider sufficient proof ...
0
votes
1answer
29 views
Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
5
votes
2answers
219 views
Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.
I saw the answers to this question: are regular languages closed under division
and the proof sketch is not ...
0
votes
2answers
25 views
Does this DFA describe this regular expression?
For the expression (ab)*ba I came up with the following (very poorly drawn):
However, this was not the correct answer - apparently the solution requires five ...
0
votes
1answer
44 views
picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}
If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$
when i pick a word for the language, would it be correct if i pick any of
these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^...
2
votes
2answers
53 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
1
vote
1answer
28 views
Fitting a regular grammar to strings from a PCFG: how big does it get?
Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$.
For finite $n$, it is always possible to find a regular ...
0
votes
2answers
41 views
What is an example of a decidable language?
I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
0
votes
0answers
25 views
Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]
I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
0
votes
2answers
45 views
if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free
I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
3
votes
1answer
64 views
Does every infinite context free language contain an infinite regular subset?
Can someone explain to me if this is true or not?
0
votes
1answer
13 views
Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$
The language was $L =\{a^n b^{n+1} : n\geq0 \}$.
This is my attempt:
I believed $L$ can also be expressed as:
$L =\{a^n b^{n}b : n\geq0 \}$
This implies that the number of $b$'s is always greater ...
4
votes
1answer
51 views
Does the following operation makes the language regular? [duplicate]
I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it.
However I thought what could happen if the language is ...
1
vote
1answer
22 views
is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.
1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
2
votes
1answer
36 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
-1
votes
1answer
25 views
Is it possible to create a regular language from an non regular language? (details inside)
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?
say L is irregular, if we add or remove finite number of ...
1
vote
1answer
58 views
Does this context-free grammar generate a regular language?
Does the following set of production rules produce a regular language or not?
$S \to AB \mid b $
$A \to SB$
$B \to AS \mid a$
I have generated following words with above grammar
$b , baa , baaaa , ...
-1
votes
0answers
26 views
Context-free grammar for the language $L_a=\{w:w \neq uu, u\in L((a + b)^*)\}$ [duplicate]
To my understanding, $(a + b)^*$ is a regular expression equivalent to the language $\{a, b\}^*$. Thus, $L_a=\{w: w \neq uu, u\in L(\{a, b\}^*)\}$.
I'm trying to simplify the language even further so ...
0
votes
1answer
31 views
Can someone explain the language L = {w: w = uu, u \in La(1*01*)}
I need help understanding the language L above.
These are my understanding:
- w = uu is a concatenation of ...
1
vote
3answers
82 views
Prove a^4n b^m is irregular using puming lemma
My assignment is to prove that the language
$L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language.
My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an ...
1
vote
1answer
60 views
Proving that co-finite languages can be decided in constant time
I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.
If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.
I'm not sure how to proceed from here. Any hints?
0
votes
0answers
41 views
Is this language with fewer b's than twice the number of a's regular?
Is $\{a^{2n}b^m|0\leq m< n\}$ regular? The lecturer said it is not and referred to the pumping lemma but isn't 2 the pumping length?
For every $n>m$ you can choose $u=\epsilon$, $v=aa$, $w$ the ...
1
vote
1answer
51 views
FSA for $(ab)^*(cb^n)^*$ [closed]
How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?
An automaton can easily be drawn for the part $(ab)^*$, but the part $(...
0
votes
0answers
16 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
10
votes
3answers
2k views
Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)
The Problem
There is no easy way to get a permutation with a regex.
Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters.
Regex: Regular ...
0
votes
1answer
28 views
Closure properties between two languages from different grammars
We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular.
What if we have a regular grammar that ...
1
vote
2answers
38 views
Show language not regular
How can I show that $\{a^ib^jc^k|i=0 \lor j=k\}$ is not regular?
I tried applying the pumping lemma but it does seem to have a pumping length of 1?
Alternatively there is the Myhill–Nerode theorem.
...
0
votes
0answers
20 views
Choice of $x,y,z$ when applying the pumping lemma [duplicate]
I want to determine whether
$$L=\big\{0^i \, 1^j \big| \,i,j \geq 1, \, i\neq j \big\}$$
is a regular language or not.
Attempt:
Let's assume that $L$ is regular. Then for $p=5$, the string $s \in ...
1
vote
1answer
91 views
PDA of the language where the number of a's are NOT equal to the number of b's
I have this NPDA for language L = {w: num_a(w) == num_b(w)}
all loops in q1
...
1
vote
1answer
37 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
1
vote
2answers
53 views
Prove or disprove L is regular
There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $L$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$
$$A \to 0A | \lambda|A1$$
...
-1
votes
1answer
15 views
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
sigma is any alphabet. R is a regular expression.
How can L(RR) even be a subset or equal to L(R)?
1
vote
0answers
59 views
What is the regular expression for the following language?
What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??
0
votes
2answers
39 views
Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages
I'm trying to create a formal algorithm in order to determine whether
two given regular expressions $a$, $a'$ define identical/equal or
unequal languages and if those languages are subsets of each ...
2
votes
1answer
59 views
Is SAT known to be non-context-free or even non-regular?
We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.
Has something similar been done for SAT?
2
votes
2answers
65 views
Prove regular languages are closed under $f(n) = 2^n$ and $ f(n) = n^2$
Suppose $ R $ is a regular language, let $ f(R) = \{ w | $ $ \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've ...
1
vote
1answer
41 views
The reverse DFA is not working as expected
Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:
And I reversed the DFA according to this answer (designing a DFA and the reverse of ...
-1
votes
2answers
61 views
Several simple propositions about regular languages
(Originally posted on Math-Stackexchange)
https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions
Notation:
$\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet
$\...
0
votes
1answer
34 views
Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular
I'm having issues using the pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{...
1
vote
1answer
48 views
How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?
How to show that the following language is not regular with the pumping lemma?
$$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
-1
votes
1answer
21 views
Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]
I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
0
votes
1answer
33 views
Can this DFA be converted to a regular expression? [duplicate]
I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
