# Questions tagged [formal-languages]

Formal languages are studied in computer science and linguistics. They are usually defined using various types of grammars (e.g. regular, context-free) and automata (e.g. deterministic and pushdown automata, Turing machines). There is a hierarchy of formal languages, which is based on the type of grammars and automata which can be used to generated them.

1,863 questions
Filter by
Sorted by
Tagged with
23 views

### Counterexamples to formal languages

Could you provide some simple Counterexamples that proof, next languages are not closed on its operations Lcf - intersection, complement Lcs - homomorphismus Lre - Complement
18 views

60 views

### Prove $L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$ is a regular language where $L$ is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma$. Prove that the language $$L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$$ is regular.
24 views

### Calculate nodes of the parse tree [closed]

Suppose that G is a context free grammar with productions that may have epsilon as the right side. If w is in L(G), the length of w is n, and w has a derivation of m steps, Show that a parse tree for ...
• 11
20 views

### Is this a PDA for balanced parentheses language?

I have got following PDA: $A=(\{p, q\},\{0, 1\},\{Z\},\delta , p, Z)$ $\delta ( p, 0, Z) = \{(p, ZZ)\}$ $\delta ( p, 1, Z) = \{(p, \lambda)\}$ $\delta ( p, \lambda, Z) = \{(q, \lambda)\}$ Assuming ...
• 1
63 views

### What does it mean for a language to be sparse?

A language $A \subseteq \sum^{*}$ is sparse, and we write $A \in SPARSE$, if there is a polynomial q such that, for all $n \in N$, $$\left|A \cap \sum^{n}\right|\leq q(n)$$ The definition of a ...
1 vote
31 views

### Prove language irregularity using Nerode theorem

Let $L=\{b^ma^n|m \space and \space n \space are \space coprime \}$ using Nerode theorem prove that $L$ is irregular. From Nerode theorem I know that $L$ is regular if and only if the number of ...
• 373
20 views

### Prerequisite on $L$ so $L^*$ is finite

I need to find a sufficient prerequisite on formal language $L$ over alphabet $\Sigma$ so that $L^*$ is a finite language. I say that language $L^*$ is finite if and only if $L = \{ \varepsilon \}$, ...
• 373
23 views

### Prove non regularity of the language a^n where n is an even or a prime number, with the pumping lemma

How to prove that the language that is the union of the language where $n$ is an even number and the language where $n$ is a prime number is non-regular with the pumping lemma? I know how to prove ...
39 views

### What is a prefix set?

I am trying to understand the following definition of prefix set - "A prefix set is a language $A \subseteq \Sigma^*$" such that no element of A is a prefix of any other element of A. I came ...
26 views

• 83
47 views

### proof that L is regular

Given that $A$ is a regular language and $B$ a regular or non-regular language, prove that $L$ is regular: $$L = \{w | wx \in \text{A such that }x \in B\}$$ We can say that L is a subset of A. Regular ...
60 views

### What exactly is this 'language' for my theory computation course saying?

In the manner of 2 + 2 telling me to add two and two together, what is this trying to say: I'm not asking for an answer (I assume it's some sort of equation), just a starting place. Thanks a million.
• 11
69 views

### What does a language parameterizing another language mean?

I am reviewing my class notes, and I came across this expression - The $n$-th slice of $A \subseteq \Sigma^*$ is $A_n = \{x \in \Sigma^* \mid {\langle n,x \rangle} \in A \}$ $C$ parameterizes $D$ (...
96 views

### $a^nb^n$ language vs $a^nb^m$

I always read that $\{a^nb^n \mid n>0\}$ is not a regular language because automata doesn't have memory, while $\{a^nb^m \mid n, m>0\}$ is regular because we don't have to remember anything ...
43 views

### Building a DFA from another DFA.

Let the language that the DFA accepts have a different definition. A word is in the language if and only if when we finish reading it we reach an accepting state AND atleast one time passed through ...
• 2,029
24 views

### Solution Verification: Prove or Disprove: If $L$ is an irregular language and $F$ is finite language, then $F\cap L^+$ is regular.

Prove or Disprove: If $L$ is an irregular language and $F$ is finite language, then $F\cap L^+$ is regular. Note: $L^+=\bigcup_{i=1}^{\infty}L^i$. I will be attempting to prove this statement. ...
• 2,029
1 vote
42 views

### Regular expression rules for union and concatenation with $\epsilon$ and $\emptyset$

I have four rules here that are true and I wanted to make sure I have a general intuition as of why. These aren't meant to be rigorous proofs, but rather simple explanations. Suppose $R$ is a regular ...
• 37
1 vote
37 views

### Natural Deduction - Restriction to closed formulas?

Is it typical for formal natural deduction systems to restrict theory axioms and deductions rules to ensure that only closed formulas (formulas with no free variables) appear in proofs? Or is the ...
• 976
24 views

• 21