# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,456 questions
Filter by
Sorted by
Tagged with
0answers
26 views

### Parsing a context free grammar, Backus Naur question

Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of ...
2answers
69 views

### Proving some subsets of a regular languages to be regular languages

I have to prove that if a language $L$ is regular then: a) $NONPREFIX(L)=\{u \in L /$none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \}$ is regular On this one I think I can ...
2answers
48 views

### Irregularity of $\{0^x1^y : y \nmid x\}$

The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular. How would one prove this using Pumping Lemma? I thought about it ...
1answer
650 views

### What does it mean for a grammar to be LR(0)?

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0). For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
1answer
69 views

### How can I show that this language is context sensitive?

I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
0answers
33 views

### Kolmogorov-Complexity of strings in decidable languages

I just recently learned about Kolmogorov-Complexity and had an idea for giving an upper bound for strings in a decidable language. Is the following statement true? Say we have a recursive language. ...
1answer
69 views

### What are the most used statements in programming (ranked)?

I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
0answers
55 views

### How to prove a statement in regular expression?

I cannot figure out how to go about proving this statement in regular expression. $$L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*)$$ Here's what I have ...
1answer
37 views

### Formal proof of language accepted by a specific CFG

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align} Please provide a formal proof for the following ...
1answer
52 views

### Proving the language of non-primes is in NP

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question. Show the following language is in ...
0answers
14 views

### Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
0answers
37 views

### How did we go from Binary to something like Python?

If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
1answer
47 views

### If two languages are decidable, can one be mapping reducible to the other?

If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
0answers
49 views

### When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not

I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. ...
4answers
561 views

### Is there a formal definition of sub-instances or sub-problems?

A decision problem is denoted as a language $L \subseteq \Sigma^{*}$. For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$. For some ...
1answer
34 views

0answers
44 views

### BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
0answers
60 views

### ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
0answers
29 views

### Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
0answers
25 views

### Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
2answers
47 views

### The intersection of 2 CFL

I have the following two CFL: $A =\{a^m b^n c^n\}$ and $B = \{a^m b^m c^n\}$. I don't understand why the intersection of this languages is $\{a^n b^n c^n\}$: can anyone explain to me why the power is ...
1answer
83 views

### Correct application of the CFL Pumping Lemma

I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable ...