Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
2answers
42 views

Show that the language of words with even sum of positions of a letter is regular

Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular. What I was thinking is to do somehow keep ...
1
vote
0answers
35 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
-2
votes
0answers
28 views

How to create instances in a post production system? [on hold]

I attempted to solve the question below and got stuck. Create a Post Production system that generates language instances which Are made up of A’s and B’s Odd numbers of A’s Have even ...
-1
votes
0answers
14 views

$L=${$a^n ww^R b^n$ | $ w \in (a+b)^+ $} [duplicate]

I read that $L=${$a^n ww^R b^n$ | $ w \in (a+b)^+ $} is Context free. any hint or idea for draw a PDA or CFG? thanks to all.
-2
votes
1answer
84 views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
-3
votes
1answer
58 views

Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
0
votes
1answer
153 views

What could 'two characters are terminals' mean?

In the context of this statement, what does 'a & b are terminals' mean? Stacks and queues can be used for determining whether a particular input string is in the language or not. L = ...
1
vote
2answers
52 views

Is string matching and replacement considered in formal languages?

Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages? For example, the family of regular languages, or the family of context free ...
1
vote
1answer
49 views

Expressive power of lexer + parser

Most modern compilers split their syntax analysis into a lexical phase that is followed by a parsing phase. The lexical phase is given by a regular expression, while parsing is guided by a ...
1
vote
1answer
49 views

Non Deterministic PDA accepted language not clear

This is a PDA from the lecture slides I'm using: They say it accepts all words that contain double a's. While it makes some sense it's not full proof. What prevents the second a to be read in the ...
1
vote
3answers
80 views

Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem Prove that the language $\qquad L = \{a^n b^j \mid n = j^2\}$ is not context free using pumping lemma. Approach taken by the book To prove such statements, the book takes the ...
1
vote
1answer
39 views

Are all Chomsky-Type3 grammars LL(1)?

Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1). If not, why is it so? Are there maybe ambiguous ...
-2
votes
1answer
38 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...
-2
votes
1answer
81 views

Is a language closed under string concatenation, repetition, and/or taking substring regular?

Is a language $L$ regular, context-free, context-sensitive, recursively enumerable, or ..., if $L$ is closed under string concatenation, and/or string repetition, and/or taking substring? ...
0
votes
1answer
50 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
4
votes
0answers
68 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
7
votes
1answer
65 views

Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Let $k\in \mathbb N$ I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : ...
3
votes
3answers
418 views

Does a logical system have semantics?

From Wikipedia: A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to ...
1
vote
2answers
119 views

What are the definitions of syntax and semantics?

For a formal language $L \subseteq \Sigma^*$ over an alphabet $\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax The syntax of a formal language is its structure, and is specified by a ...
1
vote
1answer
64 views

What are the meanings of metalanguage and metasyntax and EBNF?

I am trying to understand what BNF, metalanguage, and metasyntax are. From https://proofwiki.org/wiki/Definition:Metalanguage A metalanguage of a formal language is a formal language used to ...
-5
votes
1answer
33 views

What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-2
votes
1answer
41 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
0
votes
1answer
68 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
2
votes
1answer
29 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
5
votes
1answer
69 views

Infinite non-regular decompositions of regular languages

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case? Or, from a different ...
0
votes
1answer
39 views

Is there a PDA for every Type 3 Grammar?

we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset ...
3
votes
3answers
59 views

generate possible inputs valid for automata

I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not. Can we do the reverse ? I am looking for solution which ...
-3
votes
2answers
79 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
0
votes
1answer
36 views

CFL, pumping lemma

I have difficulty with proving that the language $ L = \{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\}$ $ w = uvxyz $ I've chosen word $ w = a^{N^2} b^N $ where $ N $ is a constant ...
2
votes
0answers
306 views

Are regular languages closed under such an operation? [duplicate]

Given a string, take all of its substrings (including the empty string). For example, given $abc$, we can form a set $\{\emptyset, a, b, c, ab, bc, abc\}$. Given a regular language, take all the ...
3
votes
2answers
95 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
5
votes
2answers
472 views

does every CFL have an ambiguous CFG?

some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states: Many [context ...
1
vote
1answer
93 views

Resolve left-rescursion

Can anybody give me a hint on how to get rid of the left recursion in the following grammar? $$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A ...
3
votes
0answers
43 views

Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need ...
3
votes
1answer
125 views

Generators of families of langauges?

From Wikipedia's definition of regular langauges The collection of regular languages over an alphabet $Σ$ is defined recursively as follows: The empty language $Ø$ is a regular language. ...
1
vote
3answers
108 views

What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

Wikipedia says: A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language. A full trio, also called a cone, is a trio ...
0
votes
2answers
41 views

Can a language be the one recognized by more than one automatons?

The language recognized by an automaton is defined as the set of strings that are accepted by the automaton. I wonder if it is possible that the languages recognized by two automatons are the same? ...
0
votes
1answer
47 views

Definition of prefixes of a string

From Wikipedia: The prefixes of a string is the set of all prefixes to a string, with respect to a given language: $$ \operatorname{Pref}_L(s) = \{t \mid s=tu \mbox { for } t,u\in ...
3
votes
1answer
43 views

Definition of the cyclic shift of a formal language?

Wikipedia says, the context-free languages are closed under the cyclic shift of $L$ (the language $\{vu : uv \in L \}$) So I am looking for the definition of the cyclic shift operation on formal ...
2
votes
1answer
29 views

Differences between substitution and rewriting?

I am continuing with my self-study of formal languages. Given two alphabets $\Sigma$ and $\Delta$, a string substitution is a mapping from $\Sigma$ to $\mathcal P(\Delta^*)$, which induces a mapping ...
5
votes
2answers
146 views

Which language families admit inductive definitions?

I am self-learning about formal languages. I learned that the family of the regular languages can be defined inductively, in terms of the operations they are closed under (namely the smallest ...
1
vote
1answer
64 views

Formal language inverse

How can you specify the "inverse" of a word, so: let's say a word consists of a's and b's the language is: $ww^{-1}$ the second word is the same as the first but every a is replaced by b and every b ...
1
vote
2answers
109 views

Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar. A formal grammar is a set of formation rules that describe how to generate the strings ...
1
vote
1answer
186 views

Why is this language over {a,b,c} regular?

The language of all words over the alphabet {a,b,c} such that the number of as in the word minus the number of cs in the word is divisible by three. How is this language regular? Lecturer ...
-1
votes
2answers
140 views

Using the Pumping Lemma to show that the language $a^n b a^n$ is not regular

I've seen a lot couple of questions regarding the pumping lemma that are pretty similar to each other and this one is unfortunately not the exception. Most likely will be this question marked as a ...
10
votes
1answer
337 views

Computational complexity vs. Chomsky hierarchy

I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general. In particular, if I know that some problem is NP-complete, does it follow that the ...
-1
votes
1answer
30 views

Construct grammar given the following language [duplicate]

Construct grammar given the following language! $ L = \{(ab)^{n+1}u(ba)^n|n>0, l_c(u) = 1, u\in\{a,c,d\}^* \}$ My interpretation in a less accurate way: $(ab)^{n+1}$ says we need to concatenate ...
1
vote
1answer
128 views

Draw a graph of DFA for a regular language

I'm trying to draw a DFA graph for the regular language where every chain: ...
1
vote
0answers
29 views

Notable decidable operations on context-sensitive languages [closed]

It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable. What are notable or ...
1
vote
2answers
45 views

Proving a language is not decideable using a reduction from Busy Beaver?

I was given this function: $F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural ...