# Tag Info

## Hot answers tagged formal-grammars

5

This is not an union of two regular languages! It's a concatenation. Note the difference, Union: $L_1 \cup L_2$ Concatenation: $\{ab : a \in L_1 \wedge b \in L_2\}$. That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by constructing two NFAs for the regular ...

3

This follows from the pumping lemma, if you examine the proof closely enough.

3

I'll just show how to build a grammar for $L_1 = \{ u\#v, |u|_a > |v|_a \}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$. The idea is to write $u\#v$ as $xay\#v$ with $x,y,v \in \{a,b\}^*$ and $|y|_a = |v|_a$. The construction of $y\#v$ is handled by the non-terminal $Z$ which "grows" it from the center. $$\... 2 Let us replace a with \nearrow and b with \searrow. Given a sequence of arrows, we construct a "walk" in which each arrow's tail starts from the preceding arrow's head. We keep track of the height. You are interested in walks which end up at or above the starting height. Given such a walk w = w_1 \ldots w_n, let i \in \{0,\ldots,n\} be the last ... 2 Here is an unambiguous grammar for strings with at least as many a's as b's. \def\L#1{{\mathcal L(#1)}}$$\begin{align} S&\to EM\mid E\\ M&\to aDM\mid aD\\ E&\to aBE\mid bAE\mid\epsilon\\ D&\to aBD\mid\epsilon\\ B&\to b\mid aBB\\ A&\to a\mid bAA\\ \end{align} The following table should help us understand the strings ...

2

Your language $L$ is not regular. Suppose that it was regular, then its complement $\overline{L}$ is also regular and the intersection $M = \{ a^j,b^k \mid j=k \vee j \not\equiv k \pmod{3} \}$ between $\overline{L}$ and $\{a^j,b^k \mid j,k \ge 0\}$ is regular. Let $n$ a sufficiently large multiple of $3$ and consider the word $a^n b^n$. By the pumping ...

2

Your informal description of your language could certainly be made more precise, in the same way as you could make the description of any (mathematical) set more precise until you've written the description out in mathematical notation. In that sense, EBNF is similar to what you get when you recast an informal description of a language into a mathematical ...

1

Sticking $w$ with its reverse together usually is not a regular language and therefore there is no natural concise way to represent that using regular expressions (at least to my knowledge) Im not really sure why you would like to find a regular expression for this language, since - as you have stated - this language is finite, and therefore regular (if you ...

1

Sure, the idea is basically that you're going to turn the first 0 into blank, and then go search for the last 1 and turn it in into blank, then go back to the beginning and proceed recursively in the same fashion. Here's an implementation on the online turing machine simulator

1

Yes, listing out all the transitions would be tedious so I'll just give you the high level algorithm (the idea is to iteratively match the first 0 with the last 1, while deleting both of them). Starting from the first symbol on the tape do the following: If the current symbol is $\varepsilon$: accept If the current symbol is $1$: reject Delete the current ...

1

Consider the word $w = 0^n1^n0^n \# 0^n1^n0^n \in L$ for a sufficiently large value of $n$. By the pumping lemma for context-free languages, we know that if $L$ is context-free then there are$a,b,c,d,e = \Sigma^*$, with $|bcd| < n$ and $|bd|>1$ such that $w=abcde$ and, for every $i \ge 0$, $a b^i c d^i e\in L$. Notice that neither $b$ nor $d$ can ...

1

You can easily transform this grammar to LL(1) by extracting the common prefix $b$ in both productions of $B$, a procedure called left-factoring. You get this: $B \to b B'$ $B' \to B c$ $B' \to c$ Then $B$ always starts with $b$ and $B'$ starts either with $b$ or with $c$ which can be desided by looking at only one input symbol.

Only top voted, non community-wiki answers of a minimum length are eligible