Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
-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|...
Duarte Grilo's user avatar
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 ...
asamsa's user avatar
  • 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 ...
user avatar
-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 ...
user164478's user avatar
-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}
user164478's user avatar
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 ...
Ziyu Mao's user avatar
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 ...
Aum Thakkar's user avatar
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 ...
codeing_monkey's user avatar
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\...
Ricardo Wehbe's user avatar
-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 |...
Jonah's user avatar
  • 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 ...
Crea Teeth's user avatar
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 ...
Theorynoob's user avatar
-2 votes
0 answers
30 views

Prove (w')^R=(w^R)'

W can be any set you want....prove (w^R)'=(w')^R
Emma's user avatar
  • 1
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 ...
Crea Teeth's user avatar
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?
user1868607's user avatar
  • 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 ...
bipartite's user avatar
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 ...
Crypton99's user avatar
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 ...
Crea Teeth's user avatar
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 ...
empty-search's user avatar
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 ...
richardIII's user avatar
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$.
CXLi's user avatar
  • 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 ...
Edward Shanahan's user avatar
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,...
wsz_fantasy's user avatar
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 ...
Max Azatian's user avatar
-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?
Abhishek's user avatar
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 ...
user avatar
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 ; ...
Emma3201's user avatar
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 ...
Priit's user avatar
  • 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 ...
Bogdan's user avatar
  • 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: ...
Francisco Aguilera's user avatar
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?
oleshkowitz's user avatar
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\}^*\ |...
Barney's user avatar
  • 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),...
pezbecoding's user avatar
-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 ...
Aland Ameer's user avatar
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 ...
Mikayla Eckel Cifrese's user avatar
-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?
Barney's user avatar
  • 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 ...
Keroten's user avatar
  • 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 ...
lafinur's user avatar
  • 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 ...
lafinur's user avatar
  • 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?
Hana's user avatar
  • 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?
Nothing Agent's user avatar
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, $...
lafinur's user avatar
  • 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). ...
Charles Averill's user avatar
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. ...
lafinur's user avatar
  • 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 ...
Lorenzo's user avatar
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 ...
LK.'s user avatar
  • 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 ...
Νικολέτα Σεβαστού's user avatar
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 ...
Jan Schultke's user avatar
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 ...
Stanley's user avatar
  • 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 ...
Juan's user avatar
  • 745

1
2 3 4 5
57