Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,049
questions
0
votes
0answers
36 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
40 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
26 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,...
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
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 ...
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 ...
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
43 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 ...
1
vote
1answer
64 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 ...
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
...
2
votes
2answers
78 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
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
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 ...
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
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, ...
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
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
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.
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 ...
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
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
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?
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 ...
0
votes
1answer
16 views
Is there a problem in this BN form language?
I am working on a simple text query language. I am using the SLY parser, which itself is an LR parser/shift-reduce parser. I am running into problems with the following language specification, but I ...
4
votes
3answers
94 views
How to give a context-sensitive grammar for a^nba^nba^nb?
I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.
3
votes
1answer
35 views
Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?
In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]
In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
0
votes
1answer
22 views
Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language
Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular?...
1
vote
1answer
24 views
A deterministic FA for $0^*1^*$ is required
A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are ...
0
votes
1answer
38 views
What are the benefits of languages that are not Turing complete?
Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization?
...
0
votes
1answer
34 views
Is there a LL(K) Grammar which is not LALR(K) Grammar?
It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
2
votes
1answer
22 views
When and what must be present on the left-hand side of the turnstile in metalogics?
Let me show the problem on an example...
An actual task from one of the former exams:
Consider a simple functional language:
$$e::= x|n|e_1e_2|\lambda x.e$$
With typing rules:
$$\...
1
vote
0answers
17 views
What's the difference between Acfg and ALLcfg
In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
1
vote
1answer
36 views
Unambiguousness and determinism of CFGs for them to be LR
I came across this statement:
Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.
I was ...
0
votes
2answers
53 views
Are Context Sensitive Languages Turing Complete? [duplicate]
Related questions:
Can regular languages be Turing complete?
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
https://stackoverflow.com/questions/14589346/is-c-...
2
votes
3answers
131 views
concatenation of context sensitive and context-free is context sensitive or not?
Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not?
I almost sure that is not, but can't prove it.
2
votes
1answer
43 views
Regularity of infinite concatenation
It is well-known that an infinite union of regular languages is not necessarily regular, since every language can be written as a union of singletons. What about infinite concatenations?
Let $\{ L_z :...
2
votes
1answer
48 views
How to reduce EQU to UNI?
Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\
\texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$
How can you prove $\texttt{EQU} \leq \texttt{UNI}$?
The idea I have so far is, to simulate the TM that ...
1
vote
1answer
37 views
Description for languages that can be solved in time(n)?
How can one describe all languages that are in
$\mathrm{TIME}(n)$?
It can't be all the regular languages only, as for example $L = \{a^n b^nw \mid w \in \Sigma^* \land n \geq 1\}$ is not regular but ...
3
votes
1answer
51 views
How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?
For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$.
I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
2
votes
2answers
34 views
Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular
I have been looking around for a good source to answer the following question.
Have read a few different sources but have not found the answer I was looking for.
The question is:
Give an example ...
