Skip to main content

Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
1 vote
1 answer
34 views

How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows: Based on this definition, how can I formally prove that any regular ...
Vegetal605's user avatar
1 vote
1 answer
37 views

Kleene star of any unary language is regular

I want to prove: Let $L \subseteq \Sigma^*$. If $\Sigma=\{a\}$, then $L^*$ is regular. I found this answer: Kleene star of an infinite unary language always yields a regular language. But I do not ...
shinichi's user avatar
2 votes
1 answer
53 views

Counting words in an unambiguous context-free grammar

Given an unambigious context-free grammar $G = (\Sigma, V, \mathcal R, S)$, is there a polynomial-time algorithm that calculates $|L(G)|$ (including the case where $|L(G)|$ is infinite)? The rough ...
Olly Britton's user avatar
0 votes
1 answer
57 views

Is the following language decidable?

Please confirm if my understanding of the below question, and my answer is correct. Is the following language decidable? Justify your answer. $L = \{\langle M_1,M_2\rangle \mid L(M_1) \cup L(M_2) = \...
Mike Q's user avatar
  • 103
-1 votes
0 answers
24 views

Construct a Regular Expression for Identifying strings containing '11' followed by an odd number of '0's

I need to construct a RE for identifying the string which contains 11 followed by an odd number of zero, this is in context for Compiler Design and then it needs to be converted into a NFA then to DFA....
Pythonicnerd's user avatar
0 votes
0 answers
19 views

Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
User's user avatar
  • 11
0 votes
2 answers
50 views

Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $a(a+b)^*$ to which i applied pumping lemma. Let the pumping length be $'p'$ and the example string be $$w=a(a+b)^{p-1}$$. The string satisfies the condition that it is at ...
Dhruv's user avatar
  • 3
0 votes
0 answers
43 views

transforming a grammar from EBNF to LL(2)

I have a grammar in EBNF and want to transform it into an LL(2) grammar. Should I omit A -> empty string ? And is there a scheme I can follow? So far I would ...
peterparker's user avatar
3 votes
0 answers
48 views

Does this endomorphism over finite automata have a name?

I found this function that can be applied onto a DFA to produce a DFA. Is there a name for it? Above: A simple DFA over the alphabet $\{0, 1\}$ Below: The resultant DFA over the alphabet $\{0\mathrm{$...
Brett Schreiber's user avatar
0 votes
0 answers
10 views

Critical Pair Determination in Knuth Bendix

In the Knuth Bendix completion algorithm, how does one identify all the critical pairs for an abstract term rewriting system? Does one have to iterate through each rule, and then identify which pairs ...
Navvye's user avatar
  • 1
0 votes
1 answer
71 views

A specific class of languages

We say a languages $L$ is permutable such that $x\in L$ if and only if a permutation of $x$ be in $L$. Does the set of permutable languages is context-free or not? I think there is a permutable ...
ErroR's user avatar
  • 1,942
1 vote
1 answer
51 views

How to prove a function is a bijection (name mangling)?

I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed. We'...
user129393192's user avatar
0 votes
0 answers
9 views

Does a Language Accepted by a Non-deterministic Turing Machine with Zero Errors Necessarily Belong to Class R

It is said that a non-deterministic Turing machine M accepts a language L with m errors if and only if: For every x in language L, M does not accept x in at most m calculation routes. for every x ...
task manager's user avatar
7 votes
1 answer
115 views

Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

Let $L$ be a language over an alphabet $\Sigma$ and let $$ \text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \} $$ $$ \text{MAX}(L) = \{ w \in ...
JimmyB's user avatar
  • 213
0 votes
0 answers
20 views

Is complement of this language context-free? [duplicate]

Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language? I know that the class of ...
Abel's user avatar
  • 1
-1 votes
1 answer
32 views

is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}

I am facing a problem with the validity of the reduction function, may I get some assist in solving this issue, please? $L=\{<G>| G$ is an undirected graph on n vertices that has a Vertex Cover $...
maya cohen's user avatar
1 vote
0 answers
41 views

Alphabet of Turing Machines and Diagonalization

When we are using a diagonalization argument, does it matter what the alphabet of the Turing machine we are using to do the diagonalization is? I think it does but I'm not 100% sure. For example, ...
confusedcius's user avatar
0 votes
0 answers
27 views

Why is it simpler to express the cut-elimination rule in general deductive systems than strictly formal systems?

This article says: Depending on the strength of the metalanguage used to define the judgments and steps, simply having a deductive system does not in itself necessarily yield an effective procedure ...
Julius Hamilton's user avatar
0 votes
0 answers
26 views

How to use Jflex to generate a lexer properly?

I was told that making lexer from scrath is really hard and that we should use built in libraries. I used an already existing example to build my program. It worked but was full of error partially ...
Oh No's user avatar
  • 11
0 votes
1 answer
47 views

Constructing a DFA that accepts the set of all binary strings that contain substrings "01" or "10"

I'm having trouble designing a DFA that accepts substrings of both 01 or 10. So far, I have constructed separate DFAs that accept the substrings "01" and "10" respectively. What I'...
picato's user avatar
  • 13
2 votes
1 answer
79 views

Graph labyrinth solving sequence

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
user555076's user avatar
1 vote
0 answers
49 views

A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
Eric_'s user avatar
  • 445
1 vote
2 answers
90 views

Subset Relations Between CFGs and Their Languages

Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
Mocak's user avatar
  • 15
0 votes
1 answer
99 views

Decidability of whether a Turing machine accepts all even-length words

In my quest to understand computability theory, I came across this question, and it made me think that I don't fully understand the theory. Is this language decidable? Is it semi-decidable, co-semi-...
maya cohen's user avatar
1 vote
0 answers
35 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
0 votes
0 answers
55 views

The formal proof that one Turing Machine computes one specific function

I have asked one similar question QA_1 "The formal proof that one Turing Machine recognizes one specific language" and the answer fills the part "It does not generate any string that is ...
An5Drama's user avatar
  • 203
0 votes
1 answer
65 views

The formal proof that one Turing Machine recognizes one specific language

When given one grammar, we can formally prove that it can recognize one language using QA_1 Since Kleene's Theorem gives the equivalence between the regular grammar and the NFA, we can also use QA_1 ...
An5Drama's user avatar
  • 203
0 votes
2 answers
48 views

Reference types

Is a reference type (agnostic of PL) the object being pointed at, or the object doing the pointing? I'm having a hard time wrapping my head around the concept fundamentally (of course, I have ...
user129393192's user avatar
0 votes
0 answers
38 views

How to determine class of formal language in Chomsky Hierachy

I recently started learning about the chomsky hierarchy and I am preparing myself for an upcoming exam. Often there are tasks to specify the smallest classification of a given formal language. How ...
smallfish's user avatar
2 votes
1 answer
42 views

Express a language containing the words with an odd amount of 0's using the languages $\{0\}$ and $\{1\}$

This is a homework question and after struggling with it for a while, I have decided to ask for help here. The task is to construct a language over the alphabet $\{0,1\}$ consisting of precisely those ...
Mark's user avatar
  • 21
1 vote
1 answer
65 views

How to show L is non-regular without pumping lemma?

$L=\{(ab)^n : n\text{ is a natural number apart from }6\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?
osdinuto's user avatar
0 votes
0 answers
42 views

Why we could run the algorithm on Linear Bounded Automata?

Suppose there is an algorithm $\mathcal{A}$ for the problem $\Pi$ that halts on any instance $x\in\Pi$. Someone tells me that we can run $\mathcal{A}$ on Linear Bounded Automata, but I can't ...
ErroR's user avatar
  • 1,942
2 votes
2 answers
420 views

Undecidability of minimal PDAs and TM machines

Consider $$L=\{<TM>:TM \text{ is a Turing machine and has minimal states}\}$$ $$L'=\{<PDA>:PDA\text{ is a PDA and has minimal states}\}$$ Which one is recursive? I think neither $L$ nor $L'...
ErroR's user avatar
  • 1,942
2 votes
1 answer
71 views

Time complexity of specific variant of Turing Machine

Assume a variant of a one-tape deterministic Turing Machine that reads and writes on the portion of the tape that the input $w$ appears (like linear bounded automata). My question is, how we could ...
ErroR's user avatar
  • 1,942
4 votes
3 answers
737 views

Notation in NFA, DFA diagrams and language

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to ...
Derek Kwon's user avatar
1 vote
3 answers
425 views

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

I've been working on proving that this language L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not Context Free. "na(x)" stands for "number of ...
Librapulpfiction's user avatar
1 vote
2 answers
82 views

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Can someone please explain me how to solve this? In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $L$ in such a way that the ...
shinichi's user avatar
0 votes
1 answer
35 views

How to handle odd word

Given the language $L = \{ a^n | \text{n is odd} \}$ I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$. But with odd, I'm ...
Robert's user avatar
  • 57
2 votes
2 answers
368 views

How to handle multiple exponents (Pumping-Lemma)

Example $L = {(ab)^na^k|n\ge k}$ When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I ...
Robert's user avatar
  • 57
1 vote
1 answer
58 views

Does a language dictate the order of the word?

Lets take the Language $$L = \{ (ab)^na^k | n \ge k \}$$ Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium? In simple ...
Robert's user avatar
  • 57
0 votes
1 answer
94 views

How to put the given context-free grammar into Chomsky Normal Form?

I have questions about how to put the grammar below in CNF - Chomsky Normal Form: S ->aAa | bBb | ВВ; A -> C; B -> S | A; C -> S | ε; I did it like this: I eliminated empty productions: ...
Crow G. F.'s user avatar
3 votes
1 answer
62 views

Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some ...
Knogger's user avatar
  • 1,202
0 votes
1 answer
54 views

Is the $L'$ regular or not? [duplicate]

Suppose $L$ is regular and we define $L'=\{x:\exists y\in L \wedge \text{ y be a subsequence of x}\}$. Could we conclude that $L'$ is regular or not? I think it's not regular because if $L=a^*b^*c^*$ ...
ErroR's user avatar
  • 1,942
1 vote
1 answer
46 views

Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage

Suppose $L=\{ww^r:w\in\Sigma^*\}$. Already, we know that we can draw a PDA for $L$ such that accept each $w\in L$ with space complexity at least $|w|$. My question is how is it possible to draw a PDA ...
ErroR's user avatar
  • 1,942
0 votes
1 answer
63 views

How it possible given string belong to given grammar

Consider this context-free grammar: $$G:\\\;\; S\to aSbb|aaSbbb|\lambda$$ Is the string $a^{2020} b^{4020}\in L(G)$? I try to derive such a string but I can't, how it possible?
ErroR's user avatar
  • 1,942
2 votes
1 answer
147 views

The complement of a particular language

We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $L={a^nb^n}$ is not ...
ErroR's user avatar
  • 1,942
3 votes
1 answer
315 views

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

I am trying to convert the below context-free grammar into Chomsky Normal Form, specifically, removing rules that have three or more variables or terminators. $$S \to A a B \;\vert\; B b C$$ $$A \to A ...
pleaseandthankyou's user avatar
0 votes
0 answers
15 views

Finding program that enumerates a language using Von Neumman's computability paradigm

Given an alphabet $\Sigma$ of $n$ elements, whenever there is some order $\leq$ over the elements of $\Sigma$, we define $s^{\leq} : \Sigma^{*} \mapsto \Sigma^{*}$ as \begin{align*} s^{\leq} \left(...
lafinur's user avatar
  • 195
1 vote
0 answers
69 views

Do there exist infinitely many languages that are RE-complete?

I would like to prove or disporove: there exists infinitely many languagess that are RE-Complete. Here is my attempt of the proof. Let $L$ be any RE-complete language. Define a padded version of $L$, ...
maya cohen's user avatar
1 vote
1 answer
55 views

Proof or disproof Fin = Fin-Complete $ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $

$ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $ Proof or disproof Fin = Fin-Complete Where Fin-Complete means that for every $ L_1,L_2 \in Fin $ there exist a valid reduction $ ...
maya cohen's user avatar

1
2 3 4 5
58