Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
1answer
9 views

Regular Expression from Context Free Grammar

The purpose of this exercise is to write a program that recognize all the words derived from this grammar. The time complexity of this program must be O(n) hence i must be able to derive a regular ...
0
votes
1answer
16 views

prove language is Context-free and not regular

I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular. So far I've got that this language is not regular because ...
3
votes
1answer
51 views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
0
votes
2answers
29 views

Push down automata what to do when there is no suitable transition

This is a question that has emerged from a recent quiz I have taken. In short Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the ...
-2
votes
1answer
45 views

How to convert this type of languages to Context Free grammar?

As I've already asked my Question about the solving Context Free Grammar $L = \{a^n b^m c^p \mid n = m + p + 2\}$ Can this language be defined by a Context Free Grammar? Now i have just changed ...
-1
votes
1answer
126 views

Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free ...
0
votes
0answers
10 views

Construction of NPDA with inequality check [duplicate]

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c ...
2
votes
2answers
129 views

Can this language be defined by a Context Free Grammer?

I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt: Question: $L = \{a^n b^m c^p \mid n = m + ...
0
votes
1answer
32 views

Proving that a set of grammars for a given finite language is decidable [duplicate]

Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$ Prove that $L \in R$. Well, I think that for a start we need to check whether or ...
4
votes
3answers
105 views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
1
vote
0answers
54 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
5
votes
2answers
258 views

Is an inverse homomorphism always a homomorphism?

Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image ...
0
votes
2answers
44 views

How does this Turing machine accept $a^n b^n$?

I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something. They give a pseudocode algorithm for an machine that accepts strings from the ...
-4
votes
1answer
28 views

Is $Σ^∗$ finite? [closed]

Suppose $Σ=\{0,1\}$; then $Σ^*$ is all combinations of $Σ$. So my question: is $Σ^*$ finite?
0
votes
0answers
58 views

The pumping lemma - Proving that this language is NOT context free

I would like to find out if this language is context free or not: $\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$. I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ ...
0
votes
3answers
40 views

Construct Turing Machine which accepts the language $ww$

I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$. Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second ...
0
votes
1answer
46 views

Context free grammar for this language [duplicate]

Is this language Context Free? $L=\{a^{n+3} b^{2m} \mid n \neq m \}$ I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars ...
-2
votes
0answers
24 views

Finite State Automata construction problem [duplicate]

Can anybody explain me how to construct deterministic finite automata for these languages: $L = \{ xwx^R \mid x, w \in \{a,b\}^+ \}$ where $x^R$ is the reverse of string $x$. $L = \{ (1^k)y \mid y = ...
0
votes
1answer
66 views

Using the pumping lemma to prove that a language is context-free [duplicate]

I am new to automata theory. Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping ...
0
votes
0answers
20 views

Prove this language is not CFL [duplicate]

I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL. I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
0
votes
1answer
38 views

How can I prove this language is not CFL? [duplicate]

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
0
votes
0answers
103 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
0
votes
0answers
107 views

For which subset of all CFG can we show that $L=\mathcal{L}(G)$

Raphael explained in the comments that there are no algorithms to show $L=\mathcal{L}(G)$ for context-free grammar. So we have to reduce our expectations and try to find a proof method. In this ...
-1
votes
0answers
41 views

Is this language CFL or not? [closed]

I have a question to find out that $L = \{a^{4k} b^l a^k\mid k\geq0, l\geq1 \} + \{a^i b^j\mid i\ne j\}$ is context free or not. I don't know from where to start solving it. I know that CFL's are ...
0
votes
1answer
40 views

How to prove that the language { ww | w ∈ {a,b}* } is / isn't context free? [duplicate]

Is the language { ww | w ∈ {a,b}* } context free? I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack. Is there a way to prove this ...
0
votes
1answer
75 views

Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

I have to determine, and prove, whether the language $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma). I tried to construct ...
1
vote
1answer
41 views

Irregularity of L = {a^i b^(j+3)| i!=j }

I have a question to find out that $L = \{a^i b^{j+3}\mid i\ne j \}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u ...
1
vote
0answers
45 views

How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?

I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when ...
-2
votes
1answer
31 views

Formal Languages and Automata Theory [duplicate]

How can I show that $L = \{a^m b^n \mid (m > n \text{ or } m < n) \text{ and } m, n ≥ 1\}$ is not a regular language.
-2
votes
1answer
22 views

Union of two languages [closed]

If I have these languages: $$\begin{align*} S&=\{a,b,c,d,e,f,g,h\}\\ A&=\{b,g\}\\ B&=\{a,b,c,d,f,h\}\\ C&=\{a,c,g\}\,, \end{align*}$$ Writing $X'$ for the complement of a set $X$, ...
0
votes
1answer
26 views

How to read this inductive language definition?

A language $L$ is defined recursively according to the following rules: $λ ∈ L$ If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$ I am not sure if strings from this language should mix from this definition. ...
6
votes
1answer
50 views

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
8
votes
0answers
57 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
-1
votes
1answer
62 views

Determine if the language is $R$

Consider the following language: $$L = \{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \}$$ determine whether or not the language is in $R$. Now, from my ...
0
votes
3answers
61 views

Reduction and decidability

Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$ I am trying to understand the following proof that this language $L$ is ...
1
vote
2answers
91 views

Tips for creating “Context Free Grammar” [duplicate]

I am new to CFG's, Can someone give me tips in creating CFG that generates some language For example $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse ...
7
votes
1answer
95 views

Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
0
votes
0answers
36 views

Context-free with single terminal symbol — regular language [duplicate]

I have the following problem to solve: Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular. It is problem 4.26 from the book "Formal models of ...
2
votes
0answers
39 views

How to use homomorphisms to prove irregularity [duplicate]

I'm a bit confused on how to use homomorphims to prove irregularity or to prove that a language is not context free. This is what I'm currently thinking: Example 1: Let $L = \{ a^{i}b^{j}c^{k} : i ...
-2
votes
1answer
49 views

Is the language given by this CFG regular? [duplicate]

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
0
votes
1answer
49 views

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$ My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such ...
9
votes
2answers
181 views

Regularity of unary languages with word lengths the sum of two resp. three squares

I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$ ...
-1
votes
1answer
61 views

Proving a language isn't regular using the pumping lemma [closed]

Let the language $$ L = \{ a^nb^m : m,n \text{ has the same integer-quotient, (ignoring the remainder) } \} $$ Show that $L$ isn't regular using the pumping-lemma. Let's assume by contradiction ...
-1
votes
1answer
36 views

union of two equivalence classes (Myhill–Nerode theorem) [closed]

Let a language, $L$ such that the equivalence relation, as defined in Myhill–Nerode theorem has $4$ equivalence classes; $A_1, \ldots, A_4$. Let $S = A_1 \cup A_2$. Is $S$ always regular? ...
1
vote
1answer
46 views

Proof that a language is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
1
vote
0answers
45 views

Formal language properties and finite state machines [closed]

What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?
1
vote
0answers
26 views

How many restricted length strings are there without significant repetitions

Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no ...
-2
votes
1answer
52 views

What is the minimal states for the language DFA?

Let the language $$L = \{ w: \text{ for any prefix } u \text{ of } w : \left|\#_o(u) - 2\cdot \#_1(u) \right| \le 2 \}$$ What is the minimal number of states for a DFA, accepting $L$? ...
2
votes
1answer
41 views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
3
votes
3answers
158 views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...