# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,456 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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....
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?
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. ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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. ...
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 ...
34 views

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 ...
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. ...
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, ...
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 ...
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 ...
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 ...