Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,816
questions
-5
votes
0
answers
17
views
DFA testing exercice ASAP please [duplicate]
I have a question :
If my word can be only AA or BB or A or B how i will write my regular expression ?
And if 0 is a par number it also may be to include ?
it is something like this : A|B|epsilon) (AA|...
1
vote
1
answer
38
views
Communication complexity of Dyck language
I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
- 11
-3
votes
2
answers
54
views
Contradiction via pumping lemma
So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user164540
-2
votes
0
answers
36
views
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y
How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days.
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
-4
votes
0
answers
35
views
How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
0
votes
0
answers
21
views
Lambda Calculus with State
I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
- 1
0
votes
1
answer
57
views
Is L={0^n 1^n ∣n≥0} context free language?
I looked through many sources which give this as an example for cfl. It also makes sense according to this:
But it fails the pumping lemma test.
Let's take n=5.
According to the Pumping Lemma, we can ...
0
votes
1
answer
43
views
Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$
From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
1
vote
1
answer
18
views
Valid rules in CSG
In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$.
Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\...
-4
votes
1
answer
26
views
Which one is an LL(2) but not an LL(1)
I'm pretty sure b and d are ll2 and not one but not 100% sure.
(a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ
B → aBb | Ʌ
(b) S → aaScc | aaBbc | aBb | ac | Ʌ
B → aBb | Ʌ
(c) S → aaScc | aaBbc | B | ac |...
- 1
1
vote
1
answer
37
views
Is the class of star-free languages just the complement to counter languages within the regular language class?
So I'm kind of confused as I'm not that deep into the algebraic theory of languages.
The wikipedia article states:
Another way to state Schützenberger's theorem is that star-free languages and ...
- 67
1
vote
2
answers
71
views
Union of non regular and regular language
So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not.
Since I found counterexamples for both cases I want to look at more ...
- 11
-2
votes
0
answers
30
views
4
votes
1
answer
342
views
Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?
I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N.
Afaik the Chomsky-Schützenberger representation ...
- 67
0
votes
0
answers
31
views
Language of words concatenated with themselves
Let $L$ be a regular language.
Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
- 2,184
-1
votes
1
answer
35
views
Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}
I'm currently having trouble coming with context free grammar to describe this language.
My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
0
votes
1
answer
55
views
Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?
So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
1
vote
1
answer
78
views
Is (a*b) or (a*b)* star-free?
Here is the proof of a∗ being star-free:
$\Sigma* = \bar{\emptyset} $
$ A∗= \overline{Σ∗(Σ∖A)Σ∗} $
Would this be a proof for $a * b$? :
$ A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)} $
For $(A * B )*$ it seems more ...
- 67
0
votes
1
answer
58
views
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
- 23
1
vote
1
answer
45
views
Do function problems have an interpretation in terms of formal languages?
In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines ...
- 111
0
votes
2
answers
89
views
How to prove that $L=\{0^m1^n\;|\; \mathbf{gcd}(m,n)=1\}$ is not regular
The pumping lemma is allowed to be used in this assignment, so I have tried to make $|0^{m+b|y|-|y|}| = |xy^b| = a!, a\ge |y|,a\ge n$ so that $gcd(|0^{m+b|y|-|y|}|,n) \neq 1$.
- 1
2
votes
0
answers
71
views
How to prove this language is irregular without using Myhill-Nerode?
I have this language that I have to prove either regular or irregular.
$$
L_3 = \{mm^rn | m^r \text{ is the reverse of } m,\ m,n \in \{a,b\}^+\}
$$
It's trivial to prove that it is in fact irregular ...
0
votes
0
answers
41
views
Is $\{ 0^{a}10^{a}1 0^{a}|a \in \mathbb{N}\}$ a context free language?
I was thinking about whether $\{ 0^{a}10^{a}10^{a}|a\in\mathbb{N} \}$ is a context-free language, and I found this post. I am not sure if my understanding is correct or not, but I guess $R = \{ (a,1,a,...
- 101
1
vote
1
answer
168
views
How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL.
In any case, i ...
- 13
-2
votes
2
answers
38
views
Is the set of all strings over $\Sigma$ countably infinite or not?
Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
- 1
6
votes
2
answers
980
views
Is the language given by the regex (ab)* star-free?
I was reading about star-free languages recently and a common example of a non-star free language is the one given by (aa)*.
I was wondering if (ab)* would also work (for an alphabet of two symbols ...
user160778
0
votes
2
answers
78
views
Can you verify the end of a function declaration through syntax analysis?
In some languages, it is expected that a function declaration be terminated by syntax that includes the function name. For example, in MODULA-2, a function is declared as shown below:
PROCEDURE P ;
...
- 11
0
votes
0
answers
25
views
Confused about decomposition in Context Free Pumping lemma
Okay so here's my current solution for the question that asks whether the language is context free:
$$L = { a^nb^{3n}c^n | \, n \geq 0 } $$
Assume by contradiction that L is context-free.
Let p be ...
- 1
4
votes
3
answers
1k
views
Are 2 independent PDAs equivalent to a turing machine?
I was thinking about the language $a^nb^nc^n$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $a$ and $b$ and the second for $b$ and $c$ and ...
- 51
0
votes
0
answers
13
views
Show that if <S2;S2,s> =>* <S2,s'>, it is not necessarily the case that <S1,s> =>* s'
I am trying to solve this proof.
In structural semantics I need to proof that:
...
1
vote
1
answer
72
views
Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free?
I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
- 76
1
vote
1
answer
75
views
Language of equal numbers of as, bs, cs in any order not context-sensitive?
In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
- 155
0
votes
0
answers
18
views
prove that the language L = { ww | w ∈ {a,b}* } is not context free [duplicate]
I came across this question presented in a past exam. I can see why the language is not context free (you can't know what the first w is, hence you are not able to duplicate it, I hope it makes sense),...
- 11
-6
votes
1
answer
55
views
Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?
I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me:
Unrecognizable languages can be accepted by a Turing machine, but the machine may ...
- 11
2
votes
3
answers
286
views
Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?
If I understand correctly, the first incompleteness theorem says that any "effectively axiomatized" formal system which is consistent must contain theorems which are independent of the ...
-1
votes
1
answer
57
views
Is { a^nb^na^n} a context-sensitive language?
The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language.
I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
- 155
1
vote
1
answer
51
views
Does this really define a 0L-system?
Looking through old exams I found a problem stated as the following:
Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism ...
- 13
0
votes
0
answers
28
views
Prove the language $a^n b^m$ where $m$ is a multiple of $n$ is not regular
Consider the problem
Show $L = \{ a^{n}b^{m}\mid m \text{ es múltiplo de } n \}$ is not regular.
I attempted the following.
Assume $L$ is regular. Then there is a natural number $p \geq 1$ such ...
- 181
0
votes
1
answer
37
views
The language of chains with twice as many $a$s as $b$s is regular?
I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:
Let $L$ be the language of all words that ...
- 181
1
vote
0
answers
31
views
What is a formal grammar equivalent to one-way stack automaton?
As the title says, is there a formal grammar characterization of the class of one-way stack languages?
- 11
-1
votes
2
answers
46
views
Understanding Language L
Given:
L := {w elementof {0,1}* : w=(010 | 10)(10 | t'), with t' elementof L}
What words can we build with these rules?
01010, 1010, what else?
Does the t' allow 010010?
0
votes
0
answers
64
views
Regular expression over $\{a, b\}$ for all words with an even number of $a$s, but without consecutive $a$s
I was given the following problem.
Problem. Give a regular expression over $\{a, b\}$ whose language is the set of all words with an even number of $a$s, but without consecutive $a$s. For example, $...
- 181
1
vote
0
answers
26
views
Can a modified Turing Machine be Turing-Complete if its Program and Data memory share the same tape?
I've been working on a fun esolang that operates under the idea that it only has program memory (an infinite, sequential list of registers that instructions and instruction arguments are loaded into). ...
- 111
0
votes
0
answers
36
views
Finding a DFA with same language as given $\epsilon$-NFA
Consider the following automaton.
How does one find a DFA with an equivalent language using an algorithm? In particular, I was requested to use the algorithm described in the answer to this question. ...
- 181
-1
votes
1
answer
170
views
Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it
Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.
For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
- 3
0
votes
1
answer
125
views
nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive
I have a question I need to give the NFA of the following language: L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa ...
- 1
3
votes
1
answer
454
views
Prove or disprove that two regular languages are equivalent
I have $L_1=\{b^*+b^*a(b+ab^*a)^*ab^*\}$ and $L_2=\{(b^*ab^*a)^*b^*\}$. I want to prove or disprove that they are equivalent.
I have proved that $L_2\subseteq L_1$ and I tried to transform the second ...
1
vote
0
answers
50
views
Regex to DFA - How do I implement parsing preferences in regex search?
I've tried a to implement a Regex to DFA converter, and it works, so far, but I don't understand how to implement "parsing preferences" in the DFA.
A classic example is $a^*$. This regex is ...
- 111
0
votes
0
answers
18
views
Decide if complement of context-free language is also a context-free language
Consider the following grammar $G$:
$$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$
Decide if ...
- 13
10
votes
3
answers
2k
views
Is there a theoretical foundation behind CSS?
You know how programming languages can be based on Lambda Calculus or the Turing Machine and SQL is based on relational algebra. Is there any such thing for CSS or any foundation that could be used ...
- 745