Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

4
votes
1answer
126 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 ...
1
vote
1answer
56 views

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?
8
votes
5answers
2k views

Finite state automata: final states

In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram. But this seems to be a fundamentally ...
0
votes
2answers
211 views

How would a Turing Machine recognize n consecutive characters

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
-1
votes
2answers
48 views

Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
3
votes
1answer
185 views

This doesn't seem like a valid regular grammar; my instructor says it is

The following is a screenshot of a lecture slide from my programming language concepts course: According to Wikipedia and other sources, a regular grammar is one that is either left linear or right ...
0
votes
0answers
13 views

Non-context free languages with word degree [duplicate]

I have stumbled across these 2 problems $L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free Given : $...
1
vote
1answer
70 views

Which word to pump in pumping lemma?

Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in ...
1
vote
1answer
117 views

DFA complexity of reverse of language recognized by “maximal” DFA

Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ ...
-2
votes
1answer
49 views

Does $R(L_1\cdot L_2)=L_2\cdot L_1$? [closed]

Does $R(L_1\cdot L_2)=L_2\cdot L_1$? Where $R$ is the reverse. I can't think about counter example
0
votes
0answers
12 views

How to convert this CFL into a CFG? [duplicate]

I'm trying to convert the following context free language into a context free grammar. $L = \{a^i b^j c^k \,|\, i+2j=4k;\, i, j, k ≥ 0\}$ I am struggling given the fact there is a large number of ...
5
votes
2answers
170 views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
0
votes
1answer
52 views

Context-free grammar from language

I'm trying to come up with a context-free grammar for the following language: $$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$ My thinking is that i can rewrite this to $$L = \{a^mb^nc^nc^m\mid 0 \le n \...
0
votes
0answers
35 views

Create a transition system where every sequence has at least twice as many $a$'s than $b$'s

Create a transition system with edges $a$ and $b$ and an initial state, such that for all possible sequences, you have that: The amount of $a$'s in the sequence is at least twice as much as the ...
1
vote
1answer
37 views

Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$

Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$ I need some tips how ...
0
votes
1answer
52 views

What does $\overline{L}^*$ signify?

Suppose that $L$ is a language. What does $\overline{L}^*$ signify? Is $\overline{L^*}$ the same as $(\overline{L})^*$?
1
vote
1answer
46 views

If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language?

Let $L = \{ a^{2^n} \mid n \ge 0 \}$, which is a non-regular language (no proof here). Let $M = (\Sigma,Q,\delta,z_0,F)$ be a DFA with $\Sigma = \{a\}$, $Q = \{z_0\}$, $\delta(z_0, a) = z_0$ and $F = \...
1
vote
0answers
51 views

Prove: If $L\in R$ then $L^*\in R$

I'm having troubles with this question. If $L\in R$, there there is a turing machine $M$ that decides it. My idea is to build a turing machine $M'$ that somehow goes over all the possible permutations ...
0
votes
1answer
48 views

Can anyone find a mapping from the set of all possible string to the natural numbers?

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$? $$h : S^* \rightarrow \mathbb{N} $$ Assume $S$ is finite. I would prefer an ...
3
votes
1answer
94 views

Any common problems solvable by DFA/NFA or PDA except recognizing languages?

I understand that DFAs recognize regular languages, and PDAs context-free languages, but these are a little bit too theoretical. I am wondering if we can implement common functions or solve common ...
0
votes
0answers
32 views

Dependency of operations of languages

I've struggled in the closure properties of the general class of languages because I couldn't use any automata concept and grammars. In specific, I'm interested in dependency of operations. (The ...
-1
votes
1answer
74 views

Write a grammar for a language $L=\{ba^{2^n}b |n\ge 1\}$ [closed]

Write a grammar for a language $$L=\{ba^{2^n}b | n\ge 1\}.$$ It's not even context-free as I think. I just can't produce it, although I've tried a lot. Now my best attempt is: \begin{aligned} S &\...
4
votes
1answer
535 views

Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
4
votes
1answer
83 views

The equational theory of regular languages has no finite set of axioms for general alphabets

According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms. Why does this imply that it has no finite set of ...
0
votes
0answers
20 views

Is there any algorithmic way to decide the equivalence classes in the nerode relation?

Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$ The Nerode relation $R_L$ says $xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$ By looking at the language : I can conclude ...
2
votes
2answers
110 views

Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime

In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular. I have not been able to solve this one: The set of ...
0
votes
0answers
10 views

How can I know when I should remove b's and when put a's? [duplicate]

I have the next language L = { a^n b^m c^p | n,m,p >= 0, n=\m or m=/p } And I have to construct a pushdown automata I don't know how to start resolving it Any suggestion? Thanks.
0
votes
1answer
32 views

Can we use Operator precedence parsing with this grammar?

This Grammar: A-->Bbab|aa B-->b I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this ...
4
votes
2answers
2k views

Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
2
votes
1answer
42 views

If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?

I am confused interpreting the statement of this question: "If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?" Should the symbol "|" (such as) be understood as ...
1
vote
1answer
43 views

Simulate $n$-PDA with $n-1$-PDA

I've heard that every $n$-PDA when $n > 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure ...
0
votes
1answer
68 views

inclusion and concatenation of languages

so for a homework assignment i need to prove the following: We have arbitrary languages L1⊆∑1*, L2⊆∑2*, L3⊆∑3*, L4⊆∑4* Prove that the followging is either true or ...
0
votes
0answers
72 views

Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0
votes
0answers
18 views

Prove that every infinite regular language has an undecidable infinite subset [duplicate]

I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due ...
0
votes
0answers
87 views

Proving decidability of language

Prove or disprove: The following language $L$ is decidable: $\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$ ...
0
votes
1answer
231 views

How to prove that language is decidable? [duplicate]

Prove or disprove: The following language $L$ is decidable: $\{ \langle M, x\rangle: M \text{ is a Turing machine and } M(x) \text{ halts in less than } |x|^2 \text{ steps} \}$ So for proving I need ...
1
vote
1answer
65 views

Proving that a Language is non-Regular

Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular. I was wondering if my intuition holds for proving this language as not regular: Let $q = \max(i, j) - \min(i, j)$. ...
0
votes
0answers
12 views

How do we determine p (pumping length) in pumping lemma for CFL? [duplicate]

This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why ...
0
votes
1answer
740 views

CFG With unambiguous if-else statement

I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'. The non-ambiguous if-else statement I took ...
0
votes
1answer
39 views

Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances

We are given NFA $A$, which for every input word $w$ has at most 10 runs over word $w$, beginning at the starting state. Show that there exists an algorithm, that converts such NFA to DFA in ...
1
vote
1answer
471 views

Is the union of two non-regular context-free languages always non-regular?

I had this question in my HW: Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular. My intuition is that it is wrong. I thought about the ...
-1
votes
1answer
67 views

What is the regular expression for strings containing at least one a and at least one b? [duplicate]

$L = \{w \in \{a, b, c\}^*\mid w\text{ contains at least one }a\text{ and at least one }b\}$. what's the proper regular expression for the following language?
0
votes
0answers
62 views

Prove that we can convert any given turing machine to a turing machine with only 3 states?

So in a book that I'm reading it says that we can convert any given Turing machine to a standard turing machine with only 6 states furthermore we can convert any given to a turing machine with only 3 ...
1
vote
1answer
230 views

What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK? is it being used anywhere? ...
3
votes
2answers
467 views

What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another?

So i came upon this thread : https://gateoverflow.in/57631/relation-between-np-recursive-and-recusive-enumerable and the guy says Every language in NP is recursive and Every language in NP is ...
-1
votes
1answer
56 views

Prove or disprove whether L is regular by definiton [duplicate]

Assume L is regular language, define 𝐿1 = {𝑣𝑤: 𝑣 ∈ 𝐿,𝑤 ∉ 𝐿}, prove or dispute L1 regular or not ?
3
votes
2answers
44 views

variable exponent in expression of a formal language

Take a look at the following expression: {(AnB)m|n>0,m>0} Or, to put it simply: the words in the language, have repeating parts consisting of, some A's followed by a single B. There are TWO school ...
0
votes
0answers
26 views

Value of k for the LL grammar?

For the language, a^n b^m c^n+m and the grammar \begin{align*} S&\to aAc \\\ A &\to aAc \mid bBc\\ B &\to bBc \mid \lambda \end{align*} What would the value of k be since this is an LL(k)...
0
votes
1answer
54 views

Does this constitute as an LL grammar?

For the language, $L(aa^*ba) \cup L(abbb^*)$ and the grammar \begin{align*}S&\to aAba \mid abbB\\ A &\to Aa \mid \lambda\\ B &\to Bb \mid \lambda \end{align*} Would the grammar above ...
2
votes
0answers
26 views

Give LL grammar for this language?

I need to give the LL grammar for the language below and explain why the grammar is LL and what the value of $k$ should be: $$L = \{ a^n c^m c^{n+m} : n \ge 1, m \ge 1 \}. $$ I have the following, ...