Stack Exchange Network

Stack Exchange network consists of 175 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

0
votes
0answers
7 views

What is the minimun type of logical system that allows to determine if formalized sentence is well-wormed formula or not boolean type?

This question has two parts. On the other hand I'd like to get a clarification what kind of theoretical and logical framework is required to implement a system that has propositional and predicate ...
0
votes
3answers
73 views

Define a finite automaton accepting the language below

$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$. About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
1
vote
0answers
31 views

Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
2
votes
1answer
29 views

Finding an unambiguous grammar of a language provided by a CFG

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
-2
votes
0answers
35 views

Give a regular expression for language L [closed]

guys! I am studying formal language now. There is a question: Give a regular expression for language L={a,bb,aa,abb,ba,bbb...}. Can anyone give me some advice? Thanks in advance!
1
vote
1answer
29 views

Can the complement of a context-free language be regular?

I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is : is it possible of the ...
0
votes
0answers
53 views

How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]

Let $L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets. $L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
2
votes
1answer
31 views

Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$

I've been stuck on this problem for a while. Any hints would be appreciated! Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
1
vote
1answer
261 views

Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular. I haven't managed to prove this, but I'm ...
1
vote
1answer
58 views

Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b \}$ is not regular. I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
1
vote
1answer
33 views

How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
1
vote
1answer
42 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
0
votes
1answer
44 views

how can one counter machine accepts a^n b^n c^n?

It is mentioned in Which languages are recognized by one-counter machines? that one counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?
-3
votes
1answer
41 views

Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$ [closed]

I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar. I need help. Thanks all of you! :)
2
votes
2answers
90 views

Can a TM recognize whether another TM recognizes a non-empty language?

Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$ Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm? My attempt: I wanted to study ...
1
vote
0answers
21 views

Proving existence of a language $L\in DTIME(n^{\log n})$ which is not in $Avg-P$

I'm struggling with the following question: Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{...
0
votes
1answer
78 views

Finding two languages satisfying conditions

Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$ Prove that there are two languages $L_1, L_2$ such that $L_1, L_2 $ are infinite. $L_1 \cup L_2 = E_{TM}$ $...
1
vote
1answer
91 views

For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free

Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
-1
votes
0answers
16 views

Converting a formal language to Context free grammer [duplicate]

I am trying to convert Regular expression L={ a^m b^n | m ≥ 0, 2m ≥ n ≥m} to a context free grammer.How can i extract the grammer?
0
votes
2answers
43 views

Regularity of a language contains more 1's than 0's

The language of all bitstrings with more 1s than 0s, i.e., $ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular. I know I should apply Pumping Lemma and the proof as well, what I cannot ...
2
votes
1answer
61 views

CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}

I know the answer which is: \begin{align} S &\rightarrow aS \mid T\\ T &\rightarrow aTbT\ \mid \varepsilon \end{align} Now, $bbaaa$ is in the language. But the given CFG cannot generate it. ...
1
vote
2answers
33 views

Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata? [duplicate]

I understand that $\phi$ is a null symbol. why concatenation of any language L with $\phi$ is $\phi$ rather than L ?
0
votes
1answer
47 views

Confused about pumping lemma, What i'm missing? [duplicate]

When I apply pumping lemma on this language: ${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular. let ${n=4}$, then $w=010000$...
0
votes
0answers
31 views

How to generate random strings from Context-Free Grammar in GNF

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ...
-1
votes
0answers
30 views

Find a context-free grammar for L={(a^n b^m)^z d^z} [duplicate]

need a CFG for the following language: $L={(a^n b^m)^z d^z}$ $m=2n, \ \ \ n,z \\$≥0 Any ideas?...
0
votes
1answer
38 views

Context free grammar for L={ ((ab)^n)^m }

I want to write a cfg for the following language: $ L = {((ab)^n)^m }$ $m,n >= 0$ this language produces (abababababab) where: $n=2, m=3 \\ or \\ n=3, m=2$ I have no idea what to do with it!
10
votes
2answers
704 views

Language involving irrational number is not a CFL

I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ ...
1
vote
1answer
53 views

Polynomial Time reducible explanation

Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct? If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X ...
0
votes
0answers
27 views

Show that the following languages are equal [duplicate]

I have the following exercise: Prove that $\{ab,aba\}^*=\{\epsilon\} \cup \{a\}\{ba,baa\}^*\{b,ba\}$. My idea was to write the words of each of the languages in the following way,for example for the ...
7
votes
1answer
104 views

Proof of Brzozowski's algorithm for DFA minimization?

Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it ...
0
votes
1answer
59 views

Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$

I've tried but I can't figure out any solution. Is there any hint for me to solve the question?
0
votes
0answers
28 views

How to check if a string is accepted by a context-sensitive grammar?

Is there an algorithm to determine membership in context-sensitive grammars?
1
vote
2answers
31 views

Program to check whether a string is accepted by an unrestricted grammar

How can I write a program to find out whether a given string is generated using a type 0 grammar (unrestricted grammar)?
3
votes
1answer
45 views

Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated. The professor hasn't given the correction. I have seen similar questions but the condition ...
3
votes
0answers
24 views

Automaton without stack for visibly pushdown languages

This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in ...
1
vote
0answers
22 views

(Non) Context Free Language…? [duplicate]

I hope you could help me as you have done before (thanks again) In a previous exam I saw this question; it is asked to identify if the language is Regular, CFL or Non CFL. In my opinion this ...
6
votes
3answers
87 views

What is language density used for?

If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as : $$ p_L(n) = | L \cap \Sigma^n | $$ I am wondering why it’s useful to study this function ...
0
votes
0answers
50 views

Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
0
votes
1answer
38 views

Is this language L context-free?

The language $$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written word x, is context-free. Can someone ...
0
votes
0answers
28 views

Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language. Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt. Proof. Suppose by ...
2
votes
2answers
48 views

Is there a way a proving a language regular/non-regular that works for every possible language?

In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-...
1
vote
1answer
56 views

Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?

Is the following true or false? Why? Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are ...
1
vote
1answer
45 views

Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?

I've been asked to write a DFA for: $\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$. I don't believe this is possible. Can anyone confirm if ...
2
votes
2answers
48 views

Union of a regular and a non-regular language

Let's say we have $L_1$ which is a regular language and $L_2$ which is not. I understand that if $L_1 \cup L_2 = \Sigma^*$ then $L_1 \cup L_2$ is a regular language. Does that implicitly mean that ...
-1
votes
1answer
41 views

Find the language from a context free grammar

I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out. $$G= (\{S,A,B,C,D,E,Z\},(0,...
1
vote
1answer
39 views

Finding the equivalence classes of a language

I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language $$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$ The best way I've ...
1
vote
1answer
377 views

Is a particular string regular (e.g is '010') regular?

If the alphabet is $\{0,1\}$, then is the string '010' regular? I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to ...
0
votes
0answers
38 views

How can I find a language from a given PDA

I have the following PDA: And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
1
vote
1answer
46 views

Let u and v be two strings. What about the reverse order of their concatenaited string?

let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$? Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
1
vote
1answer
28 views

Converting CFG from GNF to CNF

I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...