Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
2answers
75 views

Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free? $$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= ...
1
vote
1answer
70 views

Is this language regular or non-regular: {ww : w ∈ {a,b}* } [duplicate]

This is a question from a text book that's giving me some trouble. The question is: Determine whether or not this language is regular. Justify your answer. $$L = \{ww : w \in \{a,b\}^* \}$$ I ...
-1
votes
1answer
50 views

NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$

I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$. Is there a two-state NPDA ...
0
votes
1answer
34 views

True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

Question: Is the following statement true or false? If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable I thought that since every language is automatically of type 0, it follows that $A ...
4
votes
1answer
62 views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
0
votes
1answer
40 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
0
votes
1answer
38 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
3
votes
1answer
150 views

How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are: $|y|\geq1$ $|xy|\leq p$ $\forall i \geq 0:xyiz\in L$ I don't understand why the length of ...
2
votes
0answers
40 views

Removing hidden ambiguity in grammar using left factoring

I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new ...
1
vote
1answer
34 views

Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is: Find a regular grammar that generates each of the following languages: ...
0
votes
1answer
78 views

If L1 ∪ L2 and L1 are regular, is L2 also regular?

This is a problem in a theory of computation book that's stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I ...
0
votes
0answers
24 views

How these languages are context free and regular [duplicate]

I found these statements in my textbook without proof. If L is a Context Free Language over a one symbol alphabet then L is regular. Is there no context free language on one symbol ...
0
votes
1answer
56 views

Pumping Lemma confusion

I have the following language... $$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$ Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is ...
2
votes
1answer
86 views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
2
votes
1answer
134 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...
1
vote
1answer
35 views

Closure properties between 2 languages of different types [duplicate]

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
1
vote
1answer
86 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
2
votes
0answers
34 views

Tightest upper bound on length of distinguishing string in Hopcroft's algorithm

Hopcroft's algorithm is an algorithm for DFA minimization that produces a table identifying which pairs of states are distinguishable. What is the tightest possible upper bound (with proof) on the ...
0
votes
0answers
27 views

What is the procedure for converting this finite automaton into a regular expression? [duplicate]

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
0
votes
0answers
17 views

non-regular context free language with logarithmic stack usage [duplicate]

Can you suggest a context-free language $L$, which is: non-regular has a PDA which accepts all $w\in L$ and uses maximum stack space of $\log(|w|)$.
0
votes
1answer
97 views

What is meant by the notation $L(…)$?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...
0
votes
1answer
94 views

How do I show that $a^n w b^n$ is not regular?

Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused ...
0
votes
1answer
66 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
0
votes
1answer
58 views

Union of finite and non-regular language [duplicate]

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular: Prove/Disprove: $C\cup B$ isn't regular. Thoughts: My intuition says this is true, but I need an idea to prove it. Since I ...
0
votes
1answer
58 views

Three languages and how to decide if they are regular [closed]

From following languages which one is regular and why others are not?And what is the regular expression for regular one. $L_1= \{wxwy | x,y,w \in (a+b)^+\}$ $L_2 = \{xwyw | x,y,w \in (a+b)^+\}$ ...
4
votes
1answer
70 views

Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$). For example, $L=\{a^nb^n\mid ...
2
votes
1answer
364 views

Reducing a non-RE language to its complement

Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...
-1
votes
1answer
62 views

Create CFG and pushdown automaton for {ww} [duplicate]

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language $\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$. I understand how the reverse of the ...
-1
votes
1answer
38 views

Deciding Countability of Languages

Suppose we have given $\Sigma=\{a,b\}$, Which one of the following set is not countable (a) Set of all languages over $\Sigma$ (b) Set of all regular languages over $\Sigma$ (c) Set of ...
0
votes
1answer
51 views

What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers. Also, in general, are there any good methods ...
-1
votes
2answers
117 views

Pushdown Automata: CFG to PDA

I have the following grammar for a context-free language: $G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$ My question is: How ...
0
votes
0answers
42 views

$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?

It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines. It was mentioned somewhere that the language $$L = \{x\#x^R \mid ...
0
votes
0answers
53 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
1
vote
0answers
134 views

Is the complement of this language Context-Free $\{(a^nb^n)^m \mid n>0,m>0\}$?

I've been asked to decide whether a given language is a Context-Free Language (CFL). If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The ...
0
votes
2answers
46 views

what is the best way to approach the construction of nondeterministic PDA's?

I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then ...
1
vote
1answer
90 views

Kleene star and Kleene plus

Let $\Sigma$ be an alphabet. Have a look at following definitions frequently used in literature containing Kleene star and Kleene plus. $\Sigma^* := \Sigma^+ \cup \{\varepsilon\}$ $\Sigma^+ := ...
0
votes
2answers
47 views

Kleene closure, concatenation problem

If $L_1 = \emptyset$ , $L_2= \{a\}$ then what is $$L_1\cdot L_2^* \cup L_1^*$$ The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$. My Approach : $L_1^* = \{\epsilon\}$ ...
5
votes
2answers
92 views

Languages of cardinality higher than $\aleph_0$

I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or ...
0
votes
1answer
30 views

If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?
-1
votes
1answer
20 views

Language equivalence proof [duplicate]

Can anyone explain to me how the following is true for any language? $$L^+ = LL^* = L^*L$$ I'm confused because $L^*$ is the set of all words including the empty string, while $L^+$ is the set of ...
0
votes
1answer
43 views

Give an example of a non-regular language $L$ such that $L^*$ is regular [duplicate]

I can't think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ?
2
votes
1answer
100 views

Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is : 1) Recognizable by a finite-automaton. 2) ...
2
votes
1answer
27 views

Can a language recognized by a NFA be recognized by a push down or Turing machine?

Every single NFA has an equivalent DFA representation so that every language recognized by NFA is recognized by the DFA, but is it also true that the language recognized by NFA is recognized by a push ...
2
votes
0answers
60 views

Morse code is a ternary human-optimised code, is there a binary, non-machine optimised code? [closed]

Is Morse code without spaces uniquely decipherable? Discusses how Morse code isn't very clear without the third (usually) unseen element, the space. Is there a (historical?) human-optimised (vs. ...
1
vote
2answers
135 views

PDA recognising all strings with a $1$ in the second half

My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $\Sigma = \{0,1\}$ ...
6
votes
2answers
2k views

Is 0* decidable?

I found a statement (without explanation) that a language $A = 0^*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite ...
2
votes
1answer
80 views

Finite Automata — Determine if a set is regular

I have been at this for hours. The question is: Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular, where $\#(n, x)$ denotes the ...
3
votes
2answers
77 views

Decide if this language is context free

I got this question for homework: Decide if this language is context free or not: $\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$. Intuitively I think it's not ...
4
votes
1answer
58 views

Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)? As I tried with some examples to transform a grammar to it ...
1
vote
1answer
86 views

Turing Machine for strings without bbb

I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \{a, b\}$. When I ...