Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,049
questions
1
vote
2answers
99 views
CFG - Left factoring in recursive nested productions
I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
0
votes
0answers
30 views
How to prove this language is not regular?
I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
0
votes
2answers
38 views
What makes a common programming language non-context-sensitive but RE?
I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.
But I cannot pinpoint what aspect makes a programming ...
0
votes
1answer
25 views
Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s
Design a Pushdown Automata, accepting either by final state or by
empty stack to accept the set of all strings of 0’s and 1’s such that
no prefix has more 1’s than 0’s
This is a homework question,...
1
vote
4answers
349 views
What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?
Wikipedia says:
A trio is a family of languages closed under e-free homomorphism,
inverse homomorphism, and intersection with regular language.
A full trio, also called a cone, is a trio ...
5
votes
1answer
2k views
Difference between substitution, morphism, and homomorphism
In closure properties, I got confused between substitution and morphism.
1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a ...
16
votes
3answers
986 views
Algorithm to test whether a language is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
0
votes
0answers
23 views
Conditions for string substitution commutativity
Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b]
Also you can assume that a,c≠𝜀 but you ...
0
votes
1answer
22 views
Union and Difference of languages generated by grammar [closed]
So I have two languages $L = \{ w \in \{a, b \}^{\ast} \ | \ w \ \text{contains an odd number of a's} \}$ and $L^{\prime} = \{ w \in \{a, b \}^{\ast} \ | \ w \ \text{contains at least two a's} \}$.
...
0
votes
1answer
23 views
Need help understanding regular expressions
I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗...
1
vote
1answer
63 views
Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$
I want to formally write the equivalence classes of the following language:
$$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$
I understand the definition ...
1
vote
1answer
39 views
What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?
I am confused about Turing Machines that are able to decide languages that contain infinite words.
Are languages with an infinite amount of only finite strings always decidable?
How can a Turing ...
1
vote
1answer
66 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 ...
0
votes
0answers
8 views
Linux editing C files [migrated]
I want to edit a C file in linux, but I want to convert it to machine instructions and then edit the code instruction by instruction. Similar to the way gdb dumps the machine code but I want the ...
0
votes
1answer
22 views
Condition in Arden's rule
According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string.
My question: what is the problem with the ...
2
votes
2answers
77 views
Proof: There exists an irregular language L such that LLLL is regular
As title.
I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.
A senior gave me a hint that Lagrange's four square theorem ...
1
vote
2answers
31 views
Complement of languages and coNP
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.
$L^c$ is said to be the complement of the language, and it seems to be ...
1
vote
0answers
42 views
Is there a metric or distance of two languages?
Given a language $L$, I am finding a method to evaluate the advantage of an automaton to decide $L$.
My goal is to decide a language $L$ (and maybe it is not decidable for automata). If one ...
25
votes
3answers
1k views
Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$
As pointed out by sdcvvc, a word in this language can also be ...
3
votes
1answer
138 views
Can an alphabet for a Turing machine contain subsets of other alphabets?
For example;
Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?
2
votes
0answers
32 views
Pumping lemma for L = {a^i b^j c^k: i < j < k}
I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below.
Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free
...
75
votes
10answers
102k views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
1
vote
1answer
31 views
Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}
I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer ...
1
vote
1answer
98 views
Language of CFG: $S \to aS | aSbS | \varepsilon$
I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I ...
-1
votes
1answer
15 views
Is finite subset of a set which contains all non regular languages a regular set?
Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ?
I know that A is not recursive enumerable set (undecidable). So I wonder ...
2
votes
1answer
44 views
Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$
In one of my exams I needed to find a CFG for $L=\{a^ib^{2i}c^{2i} | i>1\}$.
however, it really seemed to me that it is not a CFG.
I tried to show it is not using the pumping lemma, and think I ...
0
votes
1answer
60 views
$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma
How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?
2
votes
1answer
39 views
How can the union of two 'context-free but not regular' languages be regular?
I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:
If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
1
vote
1answer
49 views
Finding the equivalence classes of a language
I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language
$$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$
The best way I've ...
1
vote
1answer
39 views
Substructural Prolog?
Substructural logic is logic without some or all of the structural rules. Is substructural Prolog, substructural logic programming possible? My question is connected with article https://link.springer....
0
votes
1answer
19 views
Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?
Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, ...
4
votes
3answers
5k views
Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$
I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language:
$L = \{a^ib^jc^k \mid \text{...
0
votes
0answers
25 views
Is this language Deterministic?
I came across this question in Peter-Linz today,
Is the language L= { a^nb^n : n>=1 } U {b} deterministic ?
My doubt is that say we have a case like this {a^5 b^6} U {b}, after popping 5 a's from the ...
1
vote
5answers
9k views
Explaining why a grammar is not LL(1)
I need some help with explaining why a grammar is not LL(1).
Let us take the following grammar:
$$
\begin{align}
S \rightarrow & aB \mid bA \mid \varepsilon \\
A \rightarrow & aS \mid bAA \\
...
1
vote
1answer
47 views
Pumping Lemma on Language with subtracted length
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given
$$ L = \{ a^k b a^{m-...
1
vote
1answer
48 views
How to characterize equivalence classes induced by Myhill-Nerode theorem?
Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
2
votes
1answer
63 views
Are Context Sensitive Grammar with Polynomial Complexity Time?
Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.
Assuming a Deterministic Parser is the one which can parse unambiguous grammars in ...
1
vote
1answer
57 views
Can CYK Parsing algorithm generate the parsing tree in O(n^3)?
I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
1
vote
1answer
121 views
Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?
The definition says that language has prefix/suffix property requires that there is no code word in the ...
1
vote
1answer
29 views
Is the difference of two context-free languages still context-free?
i am asking myself the following question:
Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right?
but I do not know how to prove it.
6
votes
2answers
81 views
Can the regular image of a context-free language be undecidable?
I just need to know the truth or falsity of a simple statement.
Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
1
vote
2answers
42 views
L(M)=L where M is a TM that can move right or stay, so L is decidable
Suppose that L(M)=L where M is a one tape TM that can move right or stay.
I need to Show that L is decidable.
I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
2
votes
1answer
54 views
Turing Machines proof notations
In context of "Computability", I have went over some proofs for Recursion
Theorem using Turing Machine description. A TM $M$ stands for a single tape
Turing machine and $\langle M \rangle$ is the ...
2
votes
2answers
50 views
Turing machine reduction task
I am having trouble solving the following task:
Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$
Prove that $D$ ...
0
votes
0answers
20 views
Is $LR(k) \subset SLR(k+1)$ for $k=1,2,…$? [duplicate]
I know that:
Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers
Does this logic hold for higher $k$'s? That is, does following fact hold?...
0
votes
0answers
29 views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
2answers
226 views
proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular [duplicate]
I am trying to prove this following theorem, can someone help please?
Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$.
If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is ...
0
votes
0answers
17 views
Proving correctness of LR parser facts
I have came across following facts while reading some compilers related text. However I did not find them in any standard reference book (mainly dragon book). Are they correct? If yes, how can we ...
0
votes
1answer
25 views
How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:
When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
2
votes
1answer
88 views
Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.
Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
