# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

1,977 questions
55 views

### Class of given language

The language given is: $$L = \{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \}$$ I have to find the class to which this language belongs. Now according to my intuition, ...
192 views

### How many languages exist over the following alphabets?

(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$. For the first two alphabets in (a), we know that there ...
51 views

### Examples of non-sparse languages

All I could find is an example of sparse language. I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the ...
32 views

### Words generated by CFG whose parse tree contain even number of $X$

Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears ...
59 views

### Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?

Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations. Is there an alternative proof that goes ...
41 views

### Language equivalent states in a deterministic parity automaton

Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are ...
139 views

60 views

86 views

### Concatenation of language to itself zero times

I was solving this question: Which of the following statement(s) is/are false? $L^0=\{\epsilon\}$ $|L^0|=0$ The answer given was None. That is, none of these statements are false and ...
41 views

### “Or” in regular expressions

I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it. One basic problem I wanted to solve was ...
654 views

### Understanding facts about regular languages, finite sets and subsets of regular languages

I am aware of following two facts related to two concepts: regular languages and finite sets: Regular languages are not closed under subset and proper subset operations. It is decidable ...
29 views

### polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$ I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$ ...
593 views

### Difference between regular language and context free language

What is nature of difference of regular language and context free language? My guess is RL - CFL = RL CFL - RL = CFL Am I correct with this?
80 views

### Both a language and its complement are not context free

Is there a language $L \subseteq \{a\}^*$ such that both $L$ and its complement are not context free?
546 views

### Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
60 views

### How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help. The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should ...
34 views

### Regularity under set difference

Let L be a regular language. Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$ How do I prove it is wrong?
71 views

### Context Free Grammar $L = \{a^i(b+c)^jd^k | i<j+k; i,j,k>0\}$

I'm trying to design a CFG that accept the words of the following language: $$L = \{a^i(b+c)^jd^k \mid i<j+k; \quad i,j,k>0\}$$ My first approximation would be to do $i = j+k$ as something ...
127 views

### Infinite Union operation of Formal Languages

Is every formal language not closed under infinite union operation ? I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any ...
39 views

### Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols

I came across the fact that The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$ So I was wondering ...
96 views

### Identification of Formal Language

$$L = \{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\}.$$ Is $L$ DCFL or not? According to me it should be DCFL since we can write $L$ as $\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\}$. So, now after ...
19 views

### Subclass of nonregulsr CFL's, closed under complementation? [duplicate]

Whether there exists a subclass of nonregular CFL's closed under complementation?
152 views

### Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free

This is problem 2.44 from Introduction to the theory of computation by Michael Sipser. If $A$ and $B$ are languages, define $A \diamond B = \{xy: x \in A \land y \in B \land |x| = |y|\}$ ...
69 views

### Transform grammar into LL(1) left-associative

I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this: ...
78 views

### General version of pumping lemma for regular languages, how many partitions to consider

The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$. The article on wikipedia says, that this ...
112 views

### Proving a language is not context-free using the pumping lemma

I had a question regarding the use of the pumping lemma for a particular language I came across. I feel like I have almost solved it, but have gotten stuck on the last steps and wanted some advice. ...
367 views

161 views

### How does TLC check liveness properties?

The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet ...
### Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$? [duplicate]
I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?