Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
1answer
12 views

Are models of computation closed under composition?

It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...
0
votes
0answers
22 views

If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

I'm trying to work out a proof by construction that $L/a$ would be regular. $a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
0
votes
2answers
72 views

Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L

I have this question in my Theoretical Computer Science class on the topic of Automata and Formal Languages. $$ λ ∈ L \iff L^2 ⊆ L^3$$ I thought of showing it by proving the contrapositive but I was ...
-2
votes
0answers
17 views

decidability-countability-grammers-languages [on hold]

L=a language M= a TM Lc= complement of L 1) L={ | M is a TM, encoded with some alphabet } ; L is recursive 2) L=set of all cfls generated by some cfg; ...
0
votes
1answer
46 views

Decidability of the language of all deterministic LBA where all states are reachable

I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a) (a) L := { < A > | A is a DFSA, where all states are ...
-1
votes
1answer
49 views

Why is it not possible to prove that two Turing Machines calculate the same function?

I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
0
votes
0answers
16 views

Is there a universal Turing machine for non-deterministic Turing machines? [on hold]

I'm studying Formal Languages and Automata Theory and I found this question. I'm not sure of knowing the answer, so I'm asking for your help. I know that a universal Turing machine can emulate any ...
2
votes
1answer
37 views

Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)

I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer): Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}...
4
votes
1answer
32 views

Language containing all unambiguous grammars

Suppose $L$ is the language of the unambiguous grammars. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar. Considering that deciding whether a ...
1
vote
1answer
35 views

Prove that a language is bounded if and only if it's finite

Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
0
votes
0answers
47 views

Whether following language is linear or not?

I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$. Now, I wanted to determine whether this language is linear or not. So, I came up with this grammar: $S \rightarrow A\thinspace|\thinspace Sc$ $A \...
2
votes
1answer
41 views

Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?
2
votes
1answer
28 views

Can't find a mistake in reduction from RE language to a non-RE language

In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I ...
0
votes
0answers
15 views

What classifier can recognize differences in two text strings immediately?

I'm playing around with the TextBlob library for python. It has in it a NaiveBayesClassifier as well as a ...
1
vote
1answer
30 views

How to propose a method to construct an automaton?

Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$ It is ...
0
votes
0answers
29 views

Why do we use CYK algorithm?

Why do we use the CYK algorithm? In my book is written that with CYK algorithm you can faster see if a word is generated by a given Grammer. However I dont get it, because I need like 5 min in order ...
-1
votes
0answers
32 views

DPDA for $\{a^mb^nc^n \mid n,m \ge 1\}$?

How do I create a DPDA for $\{a^mb^nc^n \mid n,m \ge 1\}$? I have found a solution for the similar language $\{a^nb^nc^m \mid n,m \ge 1\}$ but I am not sure, if the same reasoning applies to the DPDA ...
1
vote
1answer
33 views

Equivalence of different automata

I have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for. I know some of these are ...
-1
votes
0answers
68 views

There are languages I would define as “fermionic”, see below. What is the usual name for their theory?

What is the usual name of the theory I dubbed "fermionic languages", for want of a better term? Let me first explain the naming, from 2 examples. First, a trivial example from epistemology-fiction, ...
0
votes
0answers
47 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
44 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
30 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
29 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
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
41 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
1answer
24 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
34 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
46 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
65 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
38 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
102 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
32 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
46 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
42 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
52 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
66 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
71 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
30 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
19 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
62 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
28 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 ...